一、问题
有n个物品,它们的重量分别为weight[i]
,价值分别为value[i]
,现有一个承重为m的背包,每个物品要么拿一个,要么不拿,问背包能装下的最大价值。
二、解法
2.1 二维数组
直观的动态规划是二维数组
dp[i][j]表示在下标为0-i的物品中选择,且背包承重为j时的最大价值
最后要求dp[n-1][m]
转移方程:
dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-weight[i]]+value[i])
显然,dp[i][j]
只和前一行的前j个有关。所以可以只用一维数组。
2.2 一维滚动数组
dp[j]表示背包承重为j时的最大价值
对于二维数组来说,j可以升序遍历也可以降序遍历(反正只和前一行有关)。但是对于一维数组,由于dp[j]
刚开始就是前一行的数据,所以只能降序遍历(升序遍历,会修改前面的,导致后面的值计算错误)
public class Main
{
public static void main(String[] args) {
int[] weight={1,2,3,4};
int[] value={4,2,1,10};
int bagWeight=6;
System.out.println(solveKnapsack(weight,value,bagWeight));
}
static int solveKnapsack(int[] weight,int[] value,int bagWeight){
int n=weight.length;
int[] dp=new int[bagWeight+1];
for(int i=0;i<n;i++){
for(int j=bagWeight;j>=weight[i];j--){
dp[j]=Math.max(dp[j],dp[j-weight[i]]+value[i]);
}
}
return dp[bagWeight];
}
}