01背包完全背包：每个物体有无限个多重背包1：有限个，会我们有多少个多重背包2:二进制优化分组背包问题
01背包0，1背包定义：有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。
动态规划是不断决策求最优解的过程，
「0-1 背包」即是不断对第 i 个物品的做出决策，
「0-1」正好代表不选与选两种决定。
状态f[i][j]定义：第 i个物品，背包容量 j（体积为j） 下的最优解（最大价值）：
当前的状态依赖于之前的状态，可以理解为从初始状态f[0][0] = 0开始决策，有 N 件物品，则需要 N 次决 策，每一次对第 i 件物品的决策，状态f[i][j]不断由之前的状态更新而来。
1.简单版
1）当前背包容量够，可以选，因此需要决策选与不选第 i 个物品：
选：f[i][j] = f[i - 1][j - v[i]] + w[i]。
不选：f[i][j] = f[i - 1][j] 。
进行max操作
2）当前的背包容量j
f[i][j] = f[i - 1][j]
f(i,j)是一个数，代表一种属性，需要从不同的题目中去确定
状态表示：也就是状态转移方程。
代码
package 背包问题;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 背包01二维2 {
//状态
static int N = 1010;
static int[][] f = new int[N][N];
static int[] v = new int[N];
static int[] w = new int[N];
//接收数据
public static void main(String[] args) throws IOException {
BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
String[] nm = reader.readLine().split(" ");
int n = Integer.valueOf(nm[0]);
int m = Integer.valueOf(nm[1]);
for(int i=1;i<=n;i++){
String[] vw = reader.readLine().split(" ");
v[i] = Integer.valueOf(vw[0]);
w[i] = Integer.valueOf(vw[1]);
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j
第二种：简化版
因为状态一直用的上一次的状态，所以可以进行将j换成状态值
但是需要进行判断，如果状态值不合适就不需要更新
package 背包问题;
import java.util.Scanner;
public class 背包01一维2 {
static int N = 1010;
static int[] f = new int[N];
static int[] v = new int[N];
static int[] w = new int[N];
public static void main(String[] args) {
Scanner sc= new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i=1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=m;j>=v[i];j--){
f[j] = Math.max(f[j],f[j-v[i]]+w[i]);
}
}
System.out.println(f[m]);
}
}
完全背包：每个物体有无限个
问题：有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值
简答暴力法
不选i，选k个i
package 背包问题;
import java.util.Scanner;
public class 完全背包二维02 {
static int N =1010;
static int[][] f = new int[N][N];//选择前i个品的
static int[] v = new int[N];
static int[] w = new int[N];
//二维结构，状态，体积，价值
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i=1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){//选择不同的k
for(int k=0;k*v[i]<=j;k++){//j是当前的容量，必须容量够用才可以
f[i][j] = Math.max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
System.out.println(f[n][m]);
}
}
化简：
状态化简：
代码
package 背包问题;
import java.util.Scanner;
public class 完全背包一点5维 {
//根据
//f[i][j] = Max(f[i-1][j],f[i-1][j-v]+w,f[i-1][j-2v]+2w+...)
//f[i][j-v] = Max( f[i-1][j-v], f[i-1][j-v-v]+w+....)
//f[i][j] = max(f[i-1][j],f[i][j-v])
// 当前的状态可以根据这层的状态进行改变。
static int N = 1010;
static int[][] f = new int[N][N];
static int[] v = new int[N];
static int[] w = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i=1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
}
//1.
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k*v[i]<=j;k++){
f[i][j] = Math.max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
//2.化简的后的状态。
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j] = f[i-1][j];
if(j>=v[i]) f[i][j] = Math.max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
//
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
f[i][j] = f[i-1][j];//选
if(j-v[i]>=0) f[i][j] = Math.max(f[i][j],f[i][j-v[i]]+w[i]);
}
}
System.out.println(f[n][m]);
}
}
多重背包1：有限个，会我们有多少个
有 N 种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
有拿的件数要求。
求解将哪些物品装入背包，可使物品体积总和不超过背包容量，且价值总和最大。
输出最大价值
f[][]
v[]
w[]
s[]
暴力解：
package 背包问题;
import java.util.Scanner;
public class 多重背包问题01 {
//有 N 种物品和一个容量是 V 的背包。
//第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。
//暴力：
static int N = 110;
static int[][] f = new int[N][N];
static int[] v = new int[N];
static int[] w = new int[N];
static int[] s = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i=1;i<=n;i++){
v[i] = sc.nextInt();
w[i] = sc.nextInt();
s[i] = sc.nextInt();
}
//开始
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
for(int k=0;k<=s[i] && k*v[i]<=j;k++){//背包容量
f[i][j] = Math.max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
}
}
System.out.println(f[n][m]);
}
}
1.与完全背包的思考一样，选i和不选i，进行比较，为什么俄密友f(i-1,j)因为，当k为0时，就整好为
多重背包2:二进制优化
二进制优化多重背包
分组背包里面：每组最多有一个。体积，价值，大小
如果仍然不是很能理解的话，取
这样一个例子
:要求在一堆苹果选出n个苹果。我们传统的思维是一个一个地去选，选够n个苹果就停止。这样选择的次数就是n次
二进制优化思维就是：
现在给出一堆苹果和10个箱子，选出n个苹果
。将这一堆苹果分别按照
1,2,4,8,16,32，64，128，256，512分到10个箱子里，
那么由于任何一个数字x ∈[1,1024）
例如：
1就是第一个箱子
3:第一个加第三个
7:第一个+第二个+第三个
1023：1+2+3+4+5+6+7+8+9+10
都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次 。
这样利用二进制优化，时间复杂度就从O(n^3)降到O(n^2logS),从4*10^9降到了2*10^7。
代码：
package 背包问题;
import java.util.Scanner;
public class 多重背包问题二进制01 {
//00){
cnt++;
v[cnt] = va*s;//s个总共的体积
w[cnt] = wb*s;//s个总共的价值
}
}
//组合操作
n = cnt;
for(int i=1;i<=n;i++){
for(int j=0;j<=m;j++){
if(j
不选择第i组的第一个物品：
f(i-1,j)
选择第i组的第k个物品
f(i-1,j-v(i,k))+w[i,k];
分组背包问题
代码：
package 背包问题;
import java.util.Scanner;
public class 分组背包2 {
static int N = 1001;
static int[][] f = new int[N][N];
static int[][] v = new int[N][N];
static int[][] w = new int[N][N];
static int[] s = new int[N];
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
int m = sc.nextInt();
for(int i=1;i<=n;i++){
s[i] = sc.nextInt();
for(int j=0;j=v[i][k]) f[i][j] = Math.max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
System.out.println(f[n][m]);
}
}
