题目摘自《卡码网》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);
}
//初始化-第一列:背包大小为0
for(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)
