题目摘自《卡码网》46题
题意理解
m种材料——对应m物品
大小问n的行李箱——对应大小为n的背包
所以该问题是一个0-1背包问题,采用动态规划的一般思路来解题。
解题思路:
动规五部曲:
(1)定义二维dp数组,明确dp[i][j]的定义
dp[i][j]表示编号在[0,i]的物品任取,放入大小为j的背包内,所得的最大价值
(2)递推公式:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-weight[i]]+values[i])
(3)初始化:根据递推公式可以看出,总是由左边和上边推导当前的数值,所以初始化第一行第一列。
(4)遍历顺序:先物品后背包,先背包后物品都可以,因为二维dp数组保留了两个维度所有值。
(5)打印结果,debug.
1.二维dp数组解决0-1背包问题
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int m,n=0;m=sc.nextInt();n=sc.nextInt();int[] volumeArr=new int[m];int[] valuesArr=new int[m];for(int i=0;i<m;i++) volumeArr[i]=sc.nextInt();for(int i=0;i<m;i++) valuesArr[i]=sc.nextInt();Main obj=new Main();System.out.println(obj.sloveBagProblem(n,volumeArr,valuesArr));}public int sloveBagProblem(int bagSize,int[] volumeArr,int[] valuesArr){//定义dp数组int dp[][]=new int[volumeArr.length][bagSize+1];for (int i = 0; i <volumeArr.length; i++) {Arrays.fill(dp[i], -1);}//初始化-第一列:背包大小为0for(int i=0;i<valuesArr.length;i++) dp[i][0]=0;//初始化-第一行:能放入则放入for(int j=1;j<=bagSize;j++){if(volumeArr[0]>j){dp[0][j]=0;}else{dp[0][j]=valuesArr[0];}}//遍历:双for循环for(int i=1;i<volumeArr.length;i++){for(int j=1;j<=bagSize;j++){//判断是否能否加入if(volumeArr[i]>j){//不能放入dp[i][j]=dp[i-1][j];}else{//能放入dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-volumeArr[i]]+valuesArr[i]);}}}return dp[volumeArr.length-1][bagSize];}
}
2.一维dp数组(一维动态滚动数组)解决0-1背包问题——存储压缩
dp[j]表示背包大小为j时,任意取放物品能获得的最大价值。
递推公式:dp[j]=Math.max(dp[j],dp[j-volumeArr[i]]+valuesArr[i])
注意:前面的值会影响后面值的操作,所以在遍历背包大小时,从后往前操作,防止重复操作同一行数据,导致物品重复加入。
import java.util.Arrays;
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner sc=new Scanner(System.in);int m,n=0;m=sc.nextInt();n=sc.nextInt();int[] volumeArr=new int[m];int[] valuesArr=new int[m];for(int i=0;i<m;i++) volumeArr[i]=sc.nextInt();for(int i=0;i<m;i++) valuesArr[i]=sc.nextInt();Main obj=new Main();System.out.println(obj.sloveBagProblem(n,volumeArr,valuesArr));}public int sloveBagProblem(int bagSize,int[] volumeArr,int[] valuesArr){//定义dp数组int dp[]=new int[bagSize+1];//初始化Arrays.fill(dp,0);//遍历:双for循环for(int i=0;i<volumeArr.length;i++){for(int j=bagSize;j>=0;j--){//判断是否能否加入if(volumeArr[i]<=j){//能放入dp[j]=Math.max(dp[j],dp[j-volumeArr[i]]+valuesArr[i]);}}}return dp[bagSize];}
}
3.分析
时间复杂度:
O(m*n)
空间复杂度:
二维:O(m*n)
一维:O(n)