正式开始背包问题，背包问题还是挺难的，虽然大家可能看了很多背包问题模板代码，感觉挺简单，但基本理解的都不够深入。
如果是直接从来没听过背包问题，可以先看文字讲解慢慢了解 这是干什么的。
如果做过背包类问题，可以先看视频，很多内容，是自己平时没有考虑到位的。
背包问题，力扣上没有原题，大家先了解理论，今天就安排一道具体题目。
详细布置
01背包问题 二维
视频讲解：https://www.bilibili.com/video/BV1cg411g7Y6
import java.util.Scanner;
class Solution{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();//材料种类
int n = sc.nextInt();//行李空间
int[] weight = new int[m];
int[] value = new int[m];
for(int i = 0; i < m; i ++){
weight[i] = sc.nextInt();
}
for(int i = 0; i < m; i ++){
value[i] = sc.nextInt();
}
//定义dp数组
int[][] dp = new int[m][n+1];//行坐标是物品编号 有m个物品 0-m-1 纵坐标是行李空间 0-n
//初始化dp数组
int max = -1;
for(int j = weight[0]; j <= n; j ++){// 初始化第一行
dp[0][j] = value[0];
if(dp[0][j] > max) max = dp[0][j];
}
// 遍历和递推
for(int i = 1; i < m; i ++){
for(int j = 1; j <= n; j ++){
if(j < weight[i]) dp[i][j] = dp[i-1][j];
else dp[i][j] = Math.max(dp[i-1][j], value[i] + dp[i-1][j-weight[i]]);
if(dp[i][j] > max) max = dp[i][j];
}
}
System.out.println(max);
}
}
class Main
Error: Could not find or load main class Main
: non-zero return = 1
// 逻辑对了
01背包问题 一维
视频讲解：https://www.bilibili.com/video/BV1BU4y177kY
import java.util.Scanner;
class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int m = sc.nextInt();//材料种类
int n = sc.nextInt();//行李空间
int[] weight = new int[m];
int[] value = new int[m];
for(int i = 0; i < m; i ++){
weight[i] = sc.nextInt();
}
for(int i = 0; i < m; i ++){
value[i] = sc.nextInt();
}
//定义dp数组
int[] dp = new int[n+1];//行坐标是物品编号 有m个物品 0-m-1 纵坐标是行李空间 0-n
//初始化dp数组
dp[0] = 0;
// 遍历和递推
for(int i = 0; i < m; i ++){
for(int j = n; j >= weight[i]; j --){
dp[j] = Math.max(dp[j], value[i] + dp[j-weight[i]]);
}
}
System.out.println(dp[n]);
}
}
不用max
416. 分割等和子集
本题是 01背包的应用类题目
https://programmercarl.com/0416.%E5%88%86%E5%89%B2%E7%AD%89%E5%92%8C%E5%AD%90%E9%9B%86.html
视频讲解：https://www.bilibili.com/video/BV1rt4y1N7jE
class Solution {
public boolean canPartition(int[] nums) {
int sum = 0;
for(int i : nums) sum += i;
if(sum %2 != 0) return false;
// 容量
int n = sum / 2;
//数量
int m = nums.length;
//cost数组和value数组 nums
// dp数组
int[] dp = new int[n+1];
// 初始化
dp[0] = 0;
//遍历
for(int i = 1; i < m; i ++){
for(int j = n; j >= nums[i]; j --){
dp[j] = Math.max(dp[j], nums[i] + dp[j - nums[i]]); 已经在j这一行变化了
}
}
if(dp[n] == n) return true;//拼写
return false;
}
}
