0-1背包问题

一、问题

有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];
	}
}

上一篇:ES6进阶2.0


下一篇:java基础—Object类