很简单,因为,-1 > -2
并且您在每个级别的两个选择之间选择最大值。
编辑:我已经实现了一个解决方案,其中值被视为正数,我还对代码进行了微小的更改,如果有什么您不明白的地方,请随时询问。
#include <stdio.h>
#define min(a,b) (a < b ? a : b)
#define INF 10000000
int matrix[100][100] = {0};
int knapsack(int index, int size, int weights[],int values[]){
int take = INF;
if (index == -1){
if(size == 0) return 0;
else return INF;
}
if (matrix[index][size]!=-1)
return matrix[index][size];
for(int itemcount = 0;(itemcount * weights[index]) <= size;itemcount++){
if ((weights[index] * itemcount) <= size)
take = min(take, (values[index] * itemcount) + knapsack(index - 1, size - (itemcount * weights[index]), weights, values)); //knapsack(index) and not //knapsack(index-1)
}
matrix[index][size] = take;
return matrix[index][size];
}
int main(){
int nItems = 4;
int knapsackSize = 10;
int weights[4] = {5,4,6,3};
int values[4] = {1,1,1,1};
for(int i = 0;i < 100;i++) for(int j = 0;j < 100;j++) matrix[i][j] = -1;
printf("Min value = %d\n",knapsack(nItems-1,knapsackSize,weights,values));
return 0;
}
Ideone 上的解决方案链接:http://ideone.com/TNycZo http://ideone.com/TNycZo
这里我将无穷大视为一个大整数,以找到最小值,如果答案是无穷大,则意味着不可能创建这样的面额。