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 == B)
    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!

Categories