/**
* 有n个重量和价值分别为Wi,Vi的物品。
* 从这些物品中挑选出总重量不超过W的物品,求所有有挑选方案中价值总和的最大值
* @author haofan.whf
* @version $Id: Bag01.java, v 0.1 2018年06月14日 下午7:26 haofan.whf Exp $
*/
public class Bag01 {
//物品数量
int n = 4;
//背包容量
int W = 5;
//物品重量
int[] WArray = new int[]{2,1,3,2};
//物品价值
int[] VArray = new int[]{3,2,4,2};
//用数组来存储已经被计算过的值,用来剪枝
int[][] dp = new int[n+1][W+1];
{
for (int i = 0; i < dp.length; i++) {
for (int j = 0; j < dp[i].length; j++) {
dp[i][j] = -1;
}
}
}
//从第i个物品开始挑选总重量<j的部分
public int solution(int i, int j){
//当已经得知计算的结果时,直接返回
if(dp[i][j] >= 0){
return dp[i][j];
}
int res = 0;
if(i == n){
//已经没有剩余的物品了
res = 0;
}else if(j < WArray[i]){
//当前物品放不下,移至下一个物品
res = solution(i + 1, j);
}else{
//如果能放下则放/不放两种场景都需要计算,并取得最大值
res = Math.max(solution(i + 1, j - WArray[i]) + VArray[i]
, solution(i + 1,j));
}
dp[i][j] = res;
return res;
}
}
网友评论