11 Replies - 2111 Views - Last Post: 12 January 2005 - 06:41 PM Rate Topic: -----

#1 Boltress  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-December 04

Assignment Problem--have To Submit In 2 Days Help!

Posted 28 December 2004 - 12:50 PM

Problem Statement:

Suppose I want to make a decision rationally. One approach is to come up with several categories and weight each category according to its importance. Then I assign scores in each category to the competing alternatives, and pick the alternative with the highest total weighted score. For example, suppose I am buying a new car and I need to decide between a sedan, a minivan, or a sport-utility vehicle (SUV). In consultation with my wife, I come up with four categories

cost (weight 3)
carrying capacity (weight 2)
fuel efficiency (weight 1)
fun (weight 1)

After studying each vehicle carefully, we give them the following scores:

Vehicle Cost Carrying Capacity Fuel Efficiency Fun Total Score
Sedan 6 3 5 4 6*3+3*2+5*1+4*1 = 33
Minivan 5 5 3 2 5*3+5*2+3*1+2*1 = 30
SUV 4 6 2 6 4*3+6*2+2*1+6*1 = 32


Clearly we should purchase the sedan. Unfortunately, neither of us wants the sedan. I really want the minivan, and my wife really wants the SUV. And so begins the process of rationalization, in which we each try to tweak the numbers to make our choice come out on top. She quickly realizes that by tweaking one number, changing the weight of the fun category from 1 to 2, she can cause the SUV to win with a score of 38 (versus 37 for the sedan and 32 for the minivan). I have to work harder, but if I tweak two numbers, changing the cost score of the minivan from 5 to 6 and the efficiency score of the sedan from 5 to 4, then I can make the minivan win with a score of 33 (versus 32 for both the SUV and the sedan). Note that there are several other tweaks that each of us could have made that would have achieved our respective goals.

Given the initial weights and scores, as well as the zero-based index desired of the alternative that you want to win, determine the minimum number of tweaks needed to make your chosen alternative win. To win, your chosen alternative must end up with a score strictly higher than all the other alternatives--ties are not good enough. A single tweak involves changing the value of a particular weight or a particular score up or down by one. The same number cannot be tweaked more than once, and a tweak may not cause a weight or a score to exceed 9 or drop below 1. If no amount of tweaking can make your chosen alternative win, return -1.

Weights will be given as a int[], and scores will be given as a String[]. Element J of weights is the weight for category J, and element I of scores contains the scores for alternative I. Within element I of scores, character J represents the score for alternative I in category J. In the example above, weights would be { 3, 2, 1, 1 } and scores would be {"6354", "5532", "4626"}, with desired = 2 for the SUV and desired = 1 for the minivan.

Definition

Class: Rationalization
Method: minTweaks
Parameters: int[], String[], int
Returns: int
Method signature: int minTweaks(int[] weights, String[] scores, int desired)

Constraints

- Weights contains between 2 and 10 elements, inclusive.
- Each element of weights is between 1 and 9, inclusive.
- Scores contains between 2 and 10 elements, inclusive.
- Each element of scores contains exactly W characters, where W is the number of elements in weights.
- Each character in scores is a digit between '1' and '9', inclusive.
- Desired is between 0 and S-1, inclusive, where S is the number of elements in scores.

Examples

1) {3, 2, 1, 1}

{"6354", "5532", "4626"}

2

Returns: 1

The example above was trying to make the SUV win.


2) {3, 2, 1, 1}

{"6354", "5532", "4626"}

1

Returns: 2

The example above was trying to make the minivan win.


3) {3, 2, 1}

{"555", "333"}

1

Returns: -1

Option 1 can never beat option 0. The best it can do is tie.


4) {1, 2, 3, 3}

{"9234", "1334"}

1
Returns: 3

Unfortunately, we can't drop the weight of the first category to 0.


5) {8, 2}

{"55", "92"}

0

Returns: 6


6) {2, 8, 7, 3, 6, 5, 2, 4, 7, 2}

{"9197287893", "9492555365", "3459972761", "4886112198", "5963616776",
"6325897129", "3248793133", "7984474438", "4518544769", "1592681682"}

5

Returns: 17
_____________________________________________________________

Urgent Help Requried, have to submit a soultion by friday morning.

Please Help,
Boltress

Attached File(s)



Is This A Good Question/Topic? 0
  • +

Replies To: Assignment Problem--have To Submit In 2 Days Help!

#2 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,506
  • Joined: 12-July 02

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 28 December 2004 - 01:34 PM

That's a good assignment. Show us what you've got so far, and we'd be glad to help you along.
Was This Post Helpful? 0
  • +
  • -

#3 skyhawk133  Icon User is offline

  • Head DIC Head
  • member icon

Reputation: 1876
  • View blog
  • Posts: 20,284
  • Joined: 17-March 01

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 28 December 2004 - 01:36 PM

Yeh, I read it and after I stopped my head from spinning... I was still confused :-)
Was This Post Helpful? 0
  • +
  • -

#4 Boltress  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-December 04

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 28 December 2004 - 01:38 PM

I've been given this assignment today only and i've got nothing concrete so far, except few rough algorithms in mind.

My main problem is that i'm too busy to give it proper time and treatment.

Any help in regards to algorithm and implementation would be most welcome.

Boltress.
Was This Post Helpful? 0
  • +
  • -

#5 skyhawk133  Icon User is offline

  • Head DIC Head
  • member icon

Reputation: 1876
  • View blog
  • Posts: 20,284
  • Joined: 17-March 01

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 28 December 2004 - 01:42 PM

Give us what you've got so far in your head... pseudo code at a minimum.
Was This Post Helpful? 0
  • +
  • -

#6 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,506
  • Joined: 12-July 02

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 28 December 2004 - 02:51 PM

skyhawk133, on Dec 28 2004, 03:42 PM, said:

Give us what you've got so far in your head... pseudo code at a minimum.

Exactly. This site has some excellent coders whom can be consulted as resources, but as a rule, we don't write programs from scratch for assignment purposes.
Was This Post Helpful? 0
  • +
  • -

#7 Boltress  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-December 04

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 29 December 2004 - 05:00 AM

Ok guys, I made a rough algorithm for the above stated problem, its not that great but it should work. So here goes:


_________________________________________________________


1. get weight in an array of integer W[]

check for valid values(1 to 9)
check for no of elements(2 to 10)

2. get scores in a string array S[]

get limit of array(2 to 10)
enter the srings one by one checking each string for-
lingth of string = size of weight array
every character should be a digit between 1 to 9

set n = size of score array

3. get desire (0 to n)
let option be x

4. caldulate total score
create an integer array A[] of size same as n
create a temporary array T[]of integers with size same as weight array
repeat for every string of score array
store every string character of a single string as integer value in T[] with first character at first location and so on.
perform W[i]*T[i] and store it in A[i] for every i
select largest integer in array A and get its location
if Amax is a location x
return 0
exit
else
move to next step

5 Rationalization
Set tweak=0
find D=Amax-A[x]
store S[x] in T[] as integer numbers

arrange all the indices of W[] in a temporary array in descending order of their content
repeat for all i in the temporary array
if W[i]>D
tweak+=1
elseif W[i]+W[i-1]>D
tweak+=2
elseif W[i]+W[i-1]+W[i-2]>D
tweak+=3
-
-

elseif W[i]+...+W[i-upperbound]>D
tweak+=9
else
tweak=-1
return tweak

6 End

________________________________________________________

Ok this contains tweaking of the weights array only so if u can add the tweaking of score array also and give a composite result.

I'm trying to get a rough algo. for above case, as soon as i make it i'll post here.

Please help me implement it.


Any refinement or suggestions to improve algorithm would be most welcome.

Boltress
____________________________________________________

This post has been edited by Boltress: 29 December 2004 - 05:03 AM

Was This Post Helpful? 0
  • +
  • -

#8 Boltress  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-December 04

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 11 January 2005 - 12:02 PM

Is anybody there??

Hey guys/gals, i still HNAGING.

A little help would be highly appriciated.

Boltress
Was This Post Helpful? 0
  • +
  • -

#9 fyrestorm  Icon User is offline

  • D.I.C Lover
  • member icon

Reputation: 10
  • View blog
  • Posts: 3,113
  • Joined: 04-April 02

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 11 January 2005 - 02:44 PM

a little code would be helpful, we can't do much of anything until we have something you'd developed to work with...

here's some guidelines for the c++ forum here at d.i.c

besides your algorithm, have you attempted to start coding this project?

This post has been edited by fyrestorm: 11 January 2005 - 02:45 PM

Was This Post Helpful? 0
  • +
  • -

#10 Boltress  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-December 04

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 12 January 2005 - 12:02 AM

This is not totally based upon above algo.:


STEP 1 & 2. If u tweak weight say ‘j’, then gain made by the ‘desired’ total score is equal to the difference between score ‘j’ of ‘desired’ and score ‘j’ of ‘winner’ ( multiplied by amount of tweak, in this case +/-1 ).



STEP 3 & 4. If u tweak score say ‘j’ of ‘desired’, then the gain made by the ‘desired’ total score is equal to the weight ‘j’ (multiplied by amount of tweak, in this case +/-1 ).

#include <conio.h>
#include <iostream.h>
#include <io.h>

int t=0; //no. of tweaks
int w[4]; //weights
int s[2][4]; //scores
int tot[2]; //total scores
int d; //desired element
int g[2]; //points losing by 'd' to win
int wintot=-1; //winner total
int win=-1; //winner element

void main() {
//compute total scores
computetotal();
if(d==win) cout << t << " Tweaks"; exit(0);

//tweak weights +ve changes
int tflag=0;
for(int j=0;j<4;j++) {
tflag=0;
g[win]=s[d][j]-s[win][j];
if(g[win]>0) {
for(int i=0;i<2;i++) {
g[i]=s[d][j]-s[i][j];
if(g[i]<=tot[d]-tot[i])
tflag=1;
}
if(!tflag) {
w[j]++; //tweak weight j
t++;
}
computetotal();
if(d==win) cout << t << " Tweaks"; exit(0);
}
}

//tweak weights -ve changes

//tweak scores +ve changes

//tweak scores -ve changes

}

void computetotal() {
for(int i=0;i<2;i++) {
for(int j=0;j<4;j++)
tot[i]+=s[i][j]*w[i];
if(tot[i]>wintot) {
wintot=tot[i];
win=i;
}
}
}


I'm having problems with the SCORE section, would greatly appriciate it if somebody could do it for me or help me with it.

Boltress

This post has been edited by Boltress: 12 January 2005 - 12:04 AM

Was This Post Helpful? 0
  • +
  • -

#11 Boltress  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 6
  • Joined: 28-December 04

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 12 January 2005 - 09:40 AM

Come on guys i gave u all i had...

If u want any more feed please tell me.

Do help me would you.


Boltress
Was This Post Helpful? 0
  • +
  • -

#12 Amadeus  Icon User is offline

  • g+ + -o drink whiskey.cpp
  • member icon

Reputation: 248
  • View blog
  • Posts: 13,506
  • Joined: 12-July 02

Re: Assignment Problem--have To Submit In 2 Days Help!

Posted 12 January 2005 - 06:41 PM

I don't often say this, but I'm having a little trouble following the code. Can you comment some of the looping sections? I notice that you're using the if(d==win) conditional in a few places, but you're not setting d anywhere. I also notice you're using the exit command without including the stdlib, I'm surprised thats not throwing an error.

If you can comment each section, including desired output from each section, it may be easier to identify the problem. I can tell you that such and such a loop works as aloop, but I can't tell you if it works the way you need it to without an expected input and output.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1