Howdy, Stranger!

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

Categories

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

  • BitByBit_ThorBitByBit_Thor Member Posts: 2,444
    : 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
  • RiddickRiddick Member Posts: 41
    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.