最近在学习回顾一些模板和算法，突然翻到了背包问题，但是网上的资源都不是很如意，故自己整理了一些，方便自己学习和记录：
01背包：
给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn） 和一个可以装下总体积为m 的背包，问怎么选取这些物体，放在背包中（不超过背包的总体积），且让所取的物品价值达到最大。
import java.util.Scanner;
public class _01背包 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//物品数
int m = sc.nextInt();//大小
int[] dp = new int[m+5];//开始背包的大小
for(int i = 1; i <= n; i++) {
int v = sc.nextInt();//物品体积
int w = sc.nextInt();//物品价值
for(int j = m; j >= v; j--)
dp[j] = Math.max(dp[j], dp[j-v]+w);
}
System.out.println(dp[m]); //结果
}
}输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8完全背包：
完全背包是在01背包的基础上加了个条件——这n种物品都有无限的数量可以取，问怎样拿才可以实现价值最大化。
import java.util.Scanner;
public class _完全背包 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//物品数
int m = sc.nextInt();//大小
int[] dp = new int[m+5];//开背包质量的大小
for(int i = 1; i <= n; i++) {
int v = sc.nextInt();//物品体积
int w = sc.nextInt();//物品价值
for(int j = v; j <= m; j++)
dp[j] = Math.max(dp[j], dp[j-v]+w);
}
System.out.println(dp[m]);
}
}
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10多重背包：
多重背包是在01背包的基础上，加了个条件：第 i 件物品有ni件。
多重背包问题可以直接把i件物品全部拆开转化为01背包问题即可：
import java.util.Scanner;
public class _多重背包 {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();//物品数
int m = sc.nextInt();//大小
int[] dp = new int[m+5];//开背包质量的大小
for(int i = 1; i <= n; i++) {
int v = sc.nextInt();//物品体积
int w = sc.nextInt();//物品价值
int o = sc.nextInt();//每个物品个数
for(int q = 1; q <= o; q++){
for(int j = m; j >= v; j--)
dp[j] = Math.max(dp[j], dp[j-v]+w);
}
}
System.out.println(dp[m]);
}
}输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10
