CODEWITHSUNDEEP
algorithmknapsack-problem
user1409637
user1409637

Reputation:

knapsack algorithm variate

The question I'm having a problem is as follows:
Suppose I have a piggy-bank of given weight and I'm saving money in it using a given set of coins. At the end, I know the total weight of the piggy bank and the weights and values of the coins I was using.

I want to find out the minimum amount of money I can guarantee to be in the piggy bank, i.e. the worst case scenario. For example, if:

Then the minimum value in bank I can guarantee is 60.

The question is a knapsack variant but I'm not able to find the correct recurrence.

Thanks in advance!

Upvotes: 0

Views: 1202

Answers (3)

Pyra
Pyra

Reputation: 179

Apparently you know the problem, but you want to get a way to calculate the solution ^^.

For an exact method, you could check out branch and bound algorithms. This is a relatively easy OR method to find exact solutions for the knapsack problem, and you should find many courses on it.

Vicky submited a good solution to calculate a lower bound for the branch and bound algorithm.

Upvotes: 0

valdo
valdo

Reputation: 12951

Generally knapsack problem AFAIK has only exponential solution. That is, suppose you have a specific quantity of every type of coin. In the most general case you'll have to try all the possible combinations (not exceeding the overall weight of course).

A recursive algorithm would look like this:

const int N = /* type count*/;

const int g_Weight[N] = { ... };
const int g_Value[N] = { ... };

int CalcMinValueFrom(int weight, int i)
{
    int valBest = 0, valMy = 0;

    if (weight <= 0)
        return 0; // weight already reached

    if (i >= N)
        return -1; // out of coins

    while (true)
    {
        int valNext = CalcMinValueFrom(weight, i+1);
        if (valNext >= 0)
        {
            valNext += valMy;
            if (!valBest || (valBest > valNext))
                valBest = valNext;
        }

        valMy += g_Value[i];
        weight -= g_Weight[i];

        if (valBest && (valBest <= valMy))
            return valBest;
    }
}

// Returns the minimum value for the given weight    
int CalcMinValue(int weight)
{
    return CalcMinValueFrom(weight, 0);
}

However in specific cases there exist better solutions. If the weight is much bigger than the weight of any coin, then you may roughly estimate the result easily. Define for every coin its "efficiency" as a ratio between its value and weight. To minimize the value you should pick only coins of the least "efficiency". This solution is accurate up to the "edge effects", such as round-off and etc. (means - you can only take an integer number of coins).

Upvotes: 0

Vicky
Vicky

Reputation: 13244

The way I would approach this would be to assess each coin in the set to determine its "value density" (for want of a better term) - value divided by weight. In your example the first coin has a value density of 1, then the second coin has a value density of 30/50 = 0.6.

Then starting with a total weight of zero, apply the lowest "value density" coins you can without exceeding the given weight. Then apply the next lowest "value density" coins and so on until you achieve the given weight.

This is broadly a greedy algorithm.

Upvotes: 1

Related Questions