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).
