完全背包问题.md
题目：
- 有 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
输出样例：
10
-题解：
1.二维数组:
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
int N=sc.nextInt();
int V=sc.nextInt();
int[] v=new int[N+1];
int[] w=new int[N+1];
for(int i=1;i<=N;i++){
v[i]=sc.nextInt();
w[i]=sc.nextInt();
}
int[][] dp = new int[N + 1][V + 1];
for (int j = 0; j <= V; j++) {
dp[0][j] = 0;
}
for(int i=1;i<=N;i++){
for(int j=0;j<=V;j++){
if(j>=v[i]){
dp[i][j]=Math.max(dp[i][j-v[i]]+w[i],dp[i-1][j]);
}else{
dp[i][j]=dp[i-1][j];
}
}
}
System.out.println(dp[N][V]);
}
}
总结：
![01背包问题]()
01背包问题
题目：
- 有 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
- 看会了，就来试一试吧：经典的01背包问题
- 哈哈哈，祝你的代码状态为：
Accepted
- 要是还不会就看看这几个大佬的视频讲解吧：黑马程序员(多看几遍，多动动手)、代码随想录中的算法公开课。
- 文字版的讲解：代码随想录
- 题解：创建了二维数组 dp，其中 dp[i][j] 表示在前 i 个物品中，当背包容量为 j 时所能获得的最大价值，通过这样使用二维数组的动态规划方法，全面地考虑了放入和不放入每个物品的各种情况，最终准确地求出满足条件的背包能够装入物品的最大总价值。
- 代码：
二维数组dp数组
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int[][] dp = new int[N + 1][V + 1];
for (int j = 0; j <= V; j++) {
dp[0][j] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = 0; j <= V; j++) {
if (j >= v[i]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
System.out.println(dp[N][V]);
}
}
一维数组：
import java.util.Scanner;
public class KnapsackProblemOneDArray {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int N = scanner.nextInt();
int V = scanner.nextInt();
int[] v = new int[N + 1];
int[] w = new int[N + 1];
for (int i = 1; i <= N; i++) {
v[i] = scanner.nextInt();
w[i] = scanner.nextInt();
}
int[] dp = new int[V + 1];
for (int i = 1; i <= N; i++) {
for (int j = V; j >= v[i]; j--) {
dp[j] = Math.max(dp[j], dp[j - v[i]] + w[i]);
}
}
System.out.println(dp[V]);
}
}
