01背包问题
01背包问题
1.题目：
有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。 输出最大价值。
输入格式：
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i件物品的体积和价值。
输出格式：
输出一个整数，表示最大价值。
数据范围：
0 < N , V ≤ 1000
0 < vi , wi ≤ 1000
输入样例:
4 5
1 2
2 4
3 4
4 5
输出样例：
8
2.分析:
0-1背包问题是一种动态规划问题。是在给定背包容量限制的情况下，从一组物品中选择一些放入背包，使得背包中物品的总价值最大。每个物品只有一件，可以选择放入或不放入背包
核心思想是使用一个二维数组dp来存储子问题的解。dp数组的行表示考虑到的物品数量，列表示背包的容量。dp[i][j]的含义是，当考虑到前i个物品，且背包容量为j时，能够获得的最大价值。
算法的步骤：
初始化：创建一个二维数组dp，其大小为(N+1) x (V+1)，其中N是物品的数量，V是背包的容量。数组的所有元素初始化为0，表示在没有物品或背包容量为0时，最大价值为0。
填充数组：
通过两层循环遍历所有物品和所有可能的背包容量。外层循环遍历物品，内层循环遍历背包容量。
对于每个物品i和每个背包容量j，算法会考虑两种情况： 不放入当前物品：这种情况下，背包中的物品价值就是不考虑当前物品时的最大价值，即dp[i-1][j]。 放入当前物品：如果当前物品的体积小于或等于背包的剩余容量，那么可以考虑将这个物品放入背包。这种情况下，背包中的物品价值是当前物品的价值加上剩余容量（j-v[i-1]）能够达到的最大价值，即dp[i-1][j-v[i-1]] + w[i-1]。
输出结果：
当所有物品和所有背包容量都被考虑后，dp[N][V]就是最大价值。
这个算法的时间复杂度是O(NV)，N是物品的数量，V是背包的容量。因为算法需要遍历所有N个物品和所有V+1种可能的背包容量。空间复杂度也是O(NV)，因为需要存储一个(N+1)*(V+1)的二维数组。
3.代码
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int N = input.nextInt(); // 读取物品的数量
int V = input.nextInt(); // 读取背包的容量
int[] v = new int[N]; // 创建数组v，用于存储每个物品的体积
int[] w = new int[N]; // 创建数组w，用于存储每个物品的价值
for (int i = 0; i < N; i++) {
v[i] = input.nextInt(); // 读取第i个物品的体积
w[i] = input.nextInt(); // 读取第i个物品的价值
}
int[][] dp = new int[N + 1][V + 1];
for (int i = 1; i <= N; i++) { // 遍历每个物品
for (int j = 0; j <= V; j++) { // 遍历背包的每种容量
if (v[i - 1] > j) dp[i][j] = dp[i - 1][j]; // 如果当前物品体积大于背包容量，则不能放入，取上一行的值
else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i - 1]] + w[i - 1]); // 否则，考虑放入或不放入当前物品，取两者的最大值
}
}
System.out.println(dp[N][V]); // 输出背包容量为V时的最大价值
}
}
4. 视频
链接：https://pan.baidu.com/s/1T75uEX9TpNYi0lawskmFAw?pwd=by65 提取码：by65
注意： 题目分析视频中的14:30后面的内容，忘了说：要取物品放与不放时两者的最大值。