# ALGORITHM WANTED

Suppose my job is to buy a certain number of objects - W for a certain amount of money - \$B. Objects come in N different varieties and the cost of one object of variety i is Ci. For example if there are N = 4 varieties of objects whose costs are C1 = 3, C2 = 4, C3 = 7, C4 = 18 and I have B = \$20 with which to buy exactly W = 5 objects, then I could buy one \$7 object, one \$4 object and three \$3 objects.

I want an algorithm to solve this problem. Can anyone provide me such an algorithm preferably if possible using Dynamic programming approach.

## Comments

• : Suppose my job is to buy a certain number of objects - W for a
: certain amount of money - \$B. Objects come in N different varieties
: and the cost of one object of variety i is Ci. For example if there
: are N = 4 varieties of objects whose costs are C1 = 3, C2 = 4, C3 =
: 7, C4 = 18 and I have B = \$20 with which to buy exactly W = 5
: objects, then I could buy one \$7 object, one \$4 object and three \$3
: objects.
:
: I want an algorithm to solve this problem. Can anyone provide me
: such an algorithm preferably if possible using Dynamic programming
: approach.

First thought that comes to mind:

[code]
int* values = new int[W]
int* choice = new int[W];

//TODO: intialize the dollar value of each item

for (int i = 0; i < W; i++) choice[i] = 0;

do
{
//Check value of combination
int value = 0;
for (i = 0; i < W; i++) value += values[choice[i]];

if (value == break;

//Next combinations
int inc = W-1;
do
{
choice[inc]++;
if (choice[inc] == N)
{
choice[inc] = 0;
inc--;
if (inc < 0)
{ /* TODO: Combination could not be found */ }
}
else
inc = -1;
} while (inc != -1);

} while (1);

delete[] values;
delete[] choice;
[/code]
Best Regards,
Richard

The way I see it... Well, it's all pretty blurry
• Well can u be a little more specific. That's a Linear Programming problem. U have to set the restriction for the equations first..

Like :
-- Does it happen that u need to spent the entire amount of money available or the goal is just to buy a certain number of objects ('cuz this second doesn't make any sence as a problem)

The reason why that second part doesn't make sence is cuz u can sort the entire list and just buy the cheapest items posible...

This problem is really nice if u can think about modifying the problem and saying that for each item i there's only a certain number of them say Ti.

Simplex algorithm or Dynamic programming can help here instead of finding a solution that has to include every posible combination Akkk! what a waste!!

As for trying every combination u will have to use a recursive algorithm. And if u don't know how to do that, just simulate it using a stack that u can create on your own....for that GOOGLE

Sign In or Register to comment.

#### Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!