Knapsack Problem

讓背包裡面的物品總價值最大

1. const int N = 100, W = 100000;


2. int cost[N], weight[N];


3. int c[W + 1];   // 只需要一條陣列就夠了




5. void knapsack(int n, int w)


6. {


7.     memset(c, 0, sizeof(c));




9.     for (int i = 0; i < n; ++i)


10.         for (int j = w; j - weight[i] >= 0; --j)    // 由後往前


11.             c[j] = max(c[j], c[j - weight[i]] + cost[i]);




13.     cout << "最高的價值為" << c[w];


14. }