这里的动态规划是根据递归改的，dp[i][j]的含义是当查看到物品索引为i，剩余空间为j的时候，此时的最大价值。
package dynamic;
public class Knapsack {
// 递归方法主方法
public static int maxValue(int[] w,int[] v,int bag){
return process(w,v,0,bag);
}
/**
不变的量：w[] 所有货物重量数组 v[]价值数组 bag背包总重量
process函数 求的是index...往后的价值
0..index-1上做了货物的选择，使得你达到的重量是alreadyW
如果返回-1，认为没有方案
如果不返回-1，则认为返回的值是真实价值
*/
// 推荐的经典方法
public static int process(int[] w,int[] v,int index,int rest){
if (rest<0){ //case 1 剩余空间不足
return -1;
}
// rest > 0
// 货物已经遍历完
if (index == w.length){ // base case2
return 0;
}
// 有货也有空间
// 不添加当前index货物
int p1 = process(w,v,index+1,rest);
// 添加当前index货物
int p2 = -1;
int p2Next = process(w,v,index+1,rest-w[index]);
if (p2Next!=-1){
p2 = v[index]+p2Next;
}
return Math.max(p1,p2);
}
public static int dpWay(int[] w,int[] v,int bag){
int N = w.length;
int[][] dp = new int[N+1][bag+1];
// dp[N][...] = 0 最底下的一列初始值为0
for (int index = N-1; index >= 0; index--) {
for (int rest = 0; rest < bag; rest++) { // rest < 0
int p1 = dp[index+1][rest];
int p2 = -1;
if (rest-w[index]>=0){
p2 = v[index] + dp[index+1][rest-w[index]];
}
dp[index][rest] = Math.max(p1,p2);
}
}
return dp[0][bag];
}
}
参看：https://www.bilibili.com/video/BV1M44y1n78z?p=20&vd_source=46d50b5d646b50dcb2a208d3946b1598
10分钟