摘要：
目录01背包问题描述实现思路穷举方法01背包算法的基本实现01一维数组实现01背包问题的描述具体实现代码二维数组实现一维数组实现多背包问题描述问题分析转载自【动态编程】三个背包问题（01背包、完整背包、多重背包）01背包问题描述给定n个物体（它们的重量为：w1、w2、……、wn，它们的值为：v1、v2、………、vn）和一个重量为W的背包，询问如何选择这些物体并将其放入背包（不超过
转载自 【动态规划】三种背包问题（01背包、完全背包、多重背包） 01背包
问题描述
给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn） 和 一个承受重量为W的背包，
问怎么选取这些物体，放在背包中（不超过背包的承重），让所取的子集达到最大价值。
实现思路
穷举法
只要给出n个物体的所有组合（子集），分别各个子集的总价值，去掉那些总重量超过背包承重W的子集之后，
对剩下的子集中找到总价值最大的那一个，就是我们想要的结果了。
由于n各物体的有2n个子集，所以上面的做法的时间复杂度将是O(2n)，除非n很小，否则时间性能消耗非常严重。
01背包算法基本实现
/**
* @Author hwj
* @Date 2020/8/16 22:09
* @Desc: 给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn） 和 一个承受重量为W的背包，
* 问怎么选取这些物体，放在背包中（不超过背包的承重），让所取的子集达到最大价值。
**/
public class package01 {
public static void main(String[] args){
//w[]：物品重量，v[]：物品价值，m：背包承重，n：物品个数，maxValue[][]：状态
int[] w = {0, 10, 3, 4, 5}; //第一个数为0，是为了让输出时，i表示有i个物品
int[] v = {0, 3, 4, 6, 7};
int m = 10;
int n = 4;
int[][] maxValue = new int[5][16];
// 01背包算法
for (int i=1; i<=n; i++) { //第一个物体 是 第1行
for (int j=0; j<=m; j++) {
// 在背包承重为 j 时，所能达到的最大价值
if (i > 0) {
// maxValue[i-1][j]：最大价值为 在承重为 j 的情况下，不放入第i物体的最大价值
maxValue[i][j] = maxValue[i-1][j];
// 当承重开始超过第i个，比较 不放入i物体 与 放入 i 物体相比
if (j >= w[i]) {
maxValue[i][j] = max(maxValue[i][j], maxValue[i-1][j-w[i]] + v[i]);
//注：maxValue[i][j]其实就是maxValue[i-1][j] 因为上面的赋值
}
} else { //初始化，只考虑一个物体
if (j >= w[1]) {
maxValue[1][j] = v[1];
}
}
}
}
System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为："+maxValue[n][m]);
System.out.println();
// 打印背包的不同承重量
System.out.print(" " + " ");
for (int i=0; i<=m; i++) {
System.out.print(i + " ");
}
System.out.println();
// 打印01背包算法 得到的状态矩阵值
for (int i=1; i<=n; i++) {
System.out.print("i="+ i +" ");
for (int j=0; j<=m; j++) {
System.out.print(maxValue[i][j]+" ");
}
System.out.println();
}
}
public static int max(int a, int b) {
if (a > b) {
return a;
}
return b;
}
}
一维数组实现 01背包
01背包还可以用一维数组实现，只不过此时的递推式 & 初始条件就需要做些改变了。
要想用一维数组存放所有状态，也就是让该数组某个时间是第 i-1 层的状态，而过一段时间之后则成为第 i 层的状态。
覆盖的过程中，应该采用从后到前的顺序遍历。首先，改写maxValue[ W ]的值。
这是由于计算 i层 的maxValue[ W-1 ] 不需要用到 i-1 的maxValue[ W ]状态，所以，maxValue[ W ]的改动不影响maxValue[ W-1 ]的计算。
以此类推，就可以在原来的数组上面不断覆盖最新一层的状态值了。
/**
* @Author hwj
* @Date 2020/8/16 22:09
* @Desc: 给定n个物体（它们的重量为：w1，w2，......，wn，价值为：v1，v2，......，vn） 和 一个承受重量为W的背包，
* 问怎么选取这些物体，放在背包中（不超过背包的承重），让所取的子集达到最大价值。
**/
public class package01 {
public static void main(String[] args){
//w[]：物品重量，v[]：物品价值，m：背包承重，n：物品个数，maxValue[][]：状态
int[] w = {0, 10, 3, 4, 5}; //第一个数为0，是为了让输出时，i表示有i个物品
int[] v = {0, 3, 4, 6, 7};
int m = 10;
int n = 4;
int[] maxValue = new int[16];
// 01背包算法
for (int i=1; i<=n; i++) {
for (int j=m; j>=w[i]; j--) {
maxValue[j] = max(maxValue[j], maxValue[j-w[i]] + v[i]);
}
//验证 结果和二维实现的输出结果完全一样
//for (int k=0; k<=m; k++) {
// System.out.print(maxValue[k] + " ");
//}
//System.out.println();
}
System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为："+maxValue[m]);
System.out.println();
// 打印背包的不同承重量
System.out.print(" " + " ");
for (int i=0; i<=m; i++) {
System.out.print(i + " ");
}
System.out.println();
// 打印01背包算法 得到的状态矩阵值
for (int i=1; i<=n; i++) {
System.out.print("i="+ i +" ");
for (int j=0; j<=m; j++) {
System.out.print(maxValue[j]+" ");
}
System.out.println();
}
}
public static int max(int a, int b) {
if (a > b) {
return a;
}
return b;
}
}
问题描述
完全背包是在01背包的基础上加了个条件——这n种物品都有无限的数量可以取，问怎样拿才可以实现价值最大化。
问题分析
虽然题意中每种有无限件，但这里有个隐藏条件：背包承重量的固定性导致每种最多只能取某个值，再多就放不下了，这个值就是W / wi。也就是说，
对于第 i 种物品，它可以取0,1,2，......，W / wi（向下取整）件。而在01背包中，对于第 i 种物品，只能取0,1件。我们可以看到，
01背包其实就是完全背包的一个特例。所以我们可以用类似01背包的思路写出完全背包的基本算法。
具体实现代码
二维数组实现
/**
* @Author hwj
* @Date 2020/8/16 23:30
* @Desc:
**/
public class PackageComplete {
public static void main(String[] args) {
int[] w = {0,10, 3, 4, 5};
int[] v = {0,3, 4, 6, 7};
int m = 10;
int n = 4;
int[][] maxValue = new int[5][16];
for (int i=1; i<=n; i++) {
for (int j=0; j<=m; j++) {
if (i > 1) {
maxValue[i][j] = maxValue[i-1][j];
//if (j >= v[i]) {
// maxValue[i][j] = max(maxValue[i][j], maxValue[i-1][j-v[i]] + w[i]);
//}
if (j/w[i] >= 1) {
int maxTmp = 0;
// 对于i个物品，进行j/w[i]次比较得到最大值；而01背包中只需要进行1次比较
for (int k=1; k<=j/w[i]; k++) {
if (maxValue[i-1][j-k*w[i]] + k*v[i] > maxTmp) {
maxTmp = maxValue[i-1][j-k*w[i]] + k*v[i];
}
}
maxValue[i][j] = max(maxValue[i][j], maxTmp);
}
} else {
//if (j >= v[0]) {
// maxValue[0][j] = w[0];
//}
if (j/w[1] >= 1) {
maxValue[1][j] = j/w[1] * v[1];
}
}
}
}
System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为："+maxValue[n][m]);
System.out.println();
// 打印背包的不同承重量
System.out.print(" " + " ");
for (int i=0; i<=m; i++) {
System.out.print(i + " ");
}
System.out.println();
// 打印01背包算法 得到的状态矩阵值
for (int i=1; i<=n; i++) {
System.out.print("i="+ i +" ");
for (int j=0; j<=m; j++) {
System.out.print(maxValue[i][j]+" ");
}
System.out.println();
}
}
public static int max(int a, int b) {
if (a > b) {
return a;
}
return b;
}
}
一维数组实现
/**
* @Author hwj
* @Date 2020/8/16 23:30
* @Desc:
**/
public class PackageComplete {
public static void main(String[] args) {
int[] w = {0,10, 3, 4, 5};
int[] v = {0,3, 4, 6, 7};
int m = 10;
int n = 4;
int[] maxValue = new int[16];
for (int i=1; i<=n; i++) {
//for (int j=m; j>=w[i]; j--) {
// 正序遍历； 01背包是逆序遍历
for (int j=w[i]; j<=m; j++) {
maxValue[j] = max(maxValue[j], maxValue[j-w[i]] + v[i]);
}
//验证 结果和二维实现的输出结果完全一样
//for (int k=0; k<=m; k++) {
// System.out.print(maxValue[k] + " ");
//}
//System.out.println();
}
System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为："+maxValue[m]);
System.out.println();
for (int i=0; i<=m; i++) {
System.out.print(maxValue[i] + " ");
}
}
public static int max(int a, int b) {
if (a > b) {
return a;
}
return b;
}
}
问题描述
多重背包是在01背包的基础上，加了个条件：第 i 件物品有ni件。
问题分析
我们考虑一下，如果所有ni都满足ni ≥ W / wi，那不就变成完全背包的问题了么。可见，完全背包的基本实现思路也可以应用到多重背包的基本实现。对于多重背包的基本实现，与完全背包是基本一样的，不同就在于物品的个数上界不再是v/c[i]而是n[i]与v/c[i]中较小的那个。所以我们要在完全背包的基本实现之上，再考虑这个上界问题。
代码实现如下所示，代码与完全背包的区别除了多了个表示物品个数的数组n[ ]之外，只在内循环的控制条件那里。
## 二维数组实现
/**
* @Author hwj
* @Date 2020/8/16 23:40
* @Desc:
**/
public class MultiplePackage {
public static void main(String[] args) {
int[] w = {0,10, 3, 4, 5};
int[] v = {0,3, 4, 6, 7};
//第i个物品对应的个数
int[] mount = {0,5,1,2,1};
int m = 10;
int n = 4;
int[][] maxValue = new int[5][16];
for (int i=1; i<=n; i++) {
for (int j=0; j<=m; j++) {
if (i > 1) {
maxValue[i][j] = maxValue[i-1][j];
if (j/w[i] >= 1) {
int maxTmp = 0;
//for (int k=1; k<=j/w[i]; k++) {
//多重背包与完全背包的区别只在内循环这里
for (int k=1; k<=j/w[i] && k<=mount[i]; k++) {
if (maxValue[i-1][j-k*w[i]] + k*v[i] > maxTmp) {
maxTmp = maxValue[i-1][j-k*w[i]] + k*v[i];
}
}
maxValue[i][j] = max(maxValue[i][j], maxTmp);
}
} else {
if (j/w[1] >= 1) {
maxValue[1][j] = j/w[1] * v[1];
}
}
}
}
System.out.println("4个物品在背包承重为10的情况下的组合的最大价值为："+maxValue[n][m]);
System.out.println();
// 打印背包的不同承重量
System.out.print(" " + " ");
for (int i=0; i<=m; i++) {
System.out.print(i + " ");
}
System.out.println();
// 打印01背包算法 得到的状态矩阵值
for (int i=1; i<=n; i++) {
System.out.print("i="+ i +" ");
for (int j=0; j<=m; j++) {
System.out.print(maxValue[i][j]+" ");
}
System.out.println();
}
}
public static int max(int a, int b) {
if (a > b) {
return a;
}
return b;
}
}