/**
* 有n个重量和价值分别为Wi,Vi的物品。
* 从这些物品中挑选出总重量不超过W的物品，求所有有挑选方案中价值总和的最大值
* DP递推解法
* @author haofan.whf
* @version $Id: Bag02.java, v 0.1 2018年06月15日 下午6:02 haofan.whf Exp $
*/
public class Bag02 {
//物品数量
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];
/**
* dp[n][j] = 0
*
* if(j < WArray[i]){
* dp[i][j] = dp[i+1][j]
* }else{
* dp[i][j] = max(dp[i+1][j], dp[i+1][j-WArray[i]]+VArray[i])
* }
*/
public void solution(){
for(int i = n - 1; i >= 0; i--){
for (int j = 0; j <= W; j++) {
if(j < WArray[i]){
dp[i][j] = dp[i+1][j];
}else{
dp[i][j] = Math.max(dp[i+1][j], dp[i+1][j-WArray[i]]+VArray[i]);
}
}
}
System.out.println(dp[0][5]);
}
}
背包问题DP解法-递推1
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门，熙熙楼的掌柜王于贵愁眉苦脸地迎上来，“玉大人，你说我怎么就摊上这事。” “怎么了？”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着，像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上，一...
- 文/苍兰香墨 我猛地睁开眼，长吁一口气：“原来是场噩梦啊……” “哼！你这毒妇竟也来了？” 一声冷哼从身侧响起，我...
