DP - Knapsack Summary
Dynamic Programming | Set 10 ( 0-1 Knapsack Problem) | GeeksforGeeks
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
Java code from http://introcs.cs.princeton.edu/java/96optimization/Knapsack.java.html
http://www.ahathinking.com/archives/95.html
假设有物体z容量2，价值vz很大，背包容量为5，如果v的循环顺序不是逆序，那么外层循环跑到物体z时，内循环在v=2时，物体z被放入背包，当v=4时，寻求最大价值，物体z放入背包，f[4]=max{f[4],f[2]+vz}，这里毫无疑问后者最大，那么此时f[2]+vz中的f[2]已经装入了一次物体z，这样一来该物体被装入背包两次了就，不符合要求，如果逆序循环v，这一问题便解决了。
0/1背包和完全背包的java解法
http://www.mathcs.emory.edu/~cheung/Courses/323/Syllabus/DynProg/knapsack1.html
Also check http://sadakurapati.wordpress.com/2013/11/30/algorithm-knapsack/
http://hi.baidu.com/findxiaoxun/item/9abf560127a155c091571868
Dynamic Programming | Set 10 ( 0-1 Knapsack Problem) | GeeksforGeeks
Given weights and values of n items, put these items in a knapsack of capacity W to get the maximum total value in the knapsack.
To consider all subsets of items, there can be two cases for every item: (1) the item is included in the optimal subset, (2) not included in the optimal set.
Therefore, the maximum value that can be obtained from n items is max of following two values.
1) Maximum value obtained by n-1 items and W weight (excluding nth item).
2) Value of nth item plus maximum value obtained by n-1 items and W minus weight of the nth item (including nth item).
Java code from http://introcs.cs.princeton.edu/java/96optimization/Knapsack.java.html
// opt[n][w] = max profit of packing items 1..n with weight limit w // sol[n][w] = does opt solution to pack items 1..n with weight limit w include item n? int[][] opt = new int[N+1][W+1]; boolean[][] sol = new boolean[N+1][W+1]; for (int n = 1; n <= N; n++) { for (int w = 1; w <= W; w++) { // don't take item n int option1 = opt[n-1][w]; // take item n int option2 = Integer.MIN_VALUE; if (weight[n] <= w) option2 = profit[n] + opt[n-1][w-weight[n]]; // select better of two options opt[n][w] = Math.max(option1, option2); sol[n][w] = (option2 > option1); } } // determine which items to take boolean[] take = new boolean[N+1]; for (int n = N, w = W; n > 0; n--) { if (sol[n][w]) { take[n] = true; w = w - weight[n]; } else { take[n] = false; } }
int knapSack(int W, int wt[], int val[], int n){ int i, w; int K[n+1][W+1]; // Build table K[][] in bottom up manner for (i = 0; i <= n; i++) { for (w = 0; w <= W; w++) { if (i==0 || w==0) K[i][w] = 0; else if (wt[i-1] <= w) K[i][w] = max(val[i-1] + K[i-1][w-wt[i-1]], K[i-1][w]); else K[i][w] = K[i-1][w]; } } return K[n][W];}http://www.ahathinking.com/archives/95.html
如果只使用一维数组f[0…v]，我们要达到的效果是：第i次循环结束后f[v]中所表示的就是使用二维数组时的f[i][v]，即前i个物体面对容量v时的最大价值。我们知道f[v]是由两个状态得来的，f[i-1][v]和f[i-1][v-c[i]]，使用一维数组时，当第i次循环之前时，f[v]实际上就是f[i-1][v]，那么怎么得到第二个子问题的值呢？事实上，如果在每次循环中我们以v=v…0的顺序推f[v]时，就能保证f[v-c[i]]存储的是f[i-1][v-c[i]]的状态。状态转移方程为：
1
| v = V...0; f(v) = max{ f(v), f(v-c[i])+w[i] } |
/* * 对于第i轮循环 * 求出了前i个物品中面对容量为v的最大价值 */ for(i = 0; i < N; ++i) { /* * 内循环实际上讲maxV[0...v]滚动覆盖前一轮的maxV[0...V] * 可输出对照使用二维数组时的情况 * j从V至0逆序是防止有的物品放入背包多次 */ for(j = V; j >= weight[i]; --j) /* weight > j 的物品不会影响状态f[0,weight[i-1]] */ { int tmp = maxV[j-weight[i]]+value[i]; maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp; } }
public static int unpack(int[] values, int[] weights, int maxWeight) {
int[] ans = new int[maxWeight + 1];
for (int i = 0; i < values.length; i++) {
for (int j = maxWeight; j >= weights[i]; j--) { // ans[j-w[i]] still keeps old value
int takeValue = values[i] + ans[j - weights[i]];
if (takeValue > ans[j]) {
ans[j] = takeValue;
}
}
}
return ans[ans.length - 1];
}
0-1背包恰好背满
在01背包中，有时问到“恰好装满背包”时的最大价值，与不要求装满背包的区别就是在初始化的时候，其实对于没有要求必须装满背包的情况下，初始化最大价值都为0，是不存在非法状态的，所有的都是合法状态，因为可以什么都不装，这个解就是0，但是如果要求恰好装满，则必须区别初始化，除了f[0]=0,其他的f[1…v]均设为-∞或者一个比较大的负数来表示该状态是非法的。
这样的初始化能够保证，如果子问题的状态是合法的（恰好装满），那么才能得到合法的状态；如果子问题状态是非法的，则当前问题的状态依然非法，即不存在恰好装满的情况。
for(i = 1; i <= V; ++i) /* 初始化非法状态 */ { maxV[i] = -100; } for(i = 0; i < N; ++i) { for(j = V; j >= weight[i]; --j) { int tmp = maxV[j-weight[i]]+value[i]; maxV[j] = (maxV[j] > tmp) ? maxV[j] : tmp; } }
0-1背包输出最优方案
一般来讲，背包问题都是求一个最优值，但是如果要求输出得到这个最优值的方案，就可以根据状态转移方程往后推，由这一状态找到上一状态，依次向前推即可。
这样就可以有两种实现方式，一种是直接根据状态转移矩阵向前推，另一种就是使用额外一个状态矩阵记录最优方案的路径.
while(i >= 0) { if(maxValue[i][j] == maxValue[i-1][j-weight[i]] + value[i]) { printf("%d ",i); j = j - weight[i]; } --i; }Also check http://sadakurapati.wordpress.com/2013/11/30/algorithm-knapsack/
http://hi.baidu.com/findxiaoxun/item/9abf560127a155c091571868
测试数据：
10,3
3,4
4,5
5,6
10,3
3,4
4,5
5,6
1
2
3
4
5
6
| //伪代码for i=1 to n for v=0 to w[i]-1 c[i,v]=c[i-1,v];//更新背包 for v=w[i] to V c[i,v]=max{c[i-1,v],c[i-1,v-w[i]]+d[i]} |
c[i][j]数组保存了1,2,3号物品依次选择后的最大价值.w[i]是第i件物品的费用，d[i]是第i件物品的价值
这个最大价值是怎么得来的呢?
从背包容量为0开始,1号物品先试,0,1,2,的容量都不能放.所以置0,背包容量为3则里面放4.这样,这一排背包容量为4,5,6,....10的时候，最佳方案都是放4.
假如1号物品放入背包.则再看2号物品.当背包容量为3的时候，最佳方案还是上一排的最价方案c为4.而背包容量为4的时候，则最佳方案为自己的价值5.背包容量为7的时候，很显然是5加上一个值了。加谁??很显然是7-4=3的时候.上一排c3的最佳方案是4.所以。总的最佳方案是5+4为9.
这样.一排一排推下去。
最右下放的数据就是最大的价值了。(注意第3排的背包容量为7的时候,最佳方案不是本身的6.而是上一排的9.说明这时候3号物品没有被选.选的是1,2号物品.所以得9.)
从以上最大价值的构造过程中可以看出。
Read full article from Dynamic Programming | Set 10 ( 0-1 Knapsack Problem) | GeeksforGeeks