1背包问题

1.1基于动态规划的01背包问题算法实现

问题描述：

动态规划算法实现（Java）：

import java.util.Scanner;public class Packageof01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//m为背包总容量，n为物品数量。int m = sc.nextInt();int n = sc.nextInt();/*carry数组:动态规划得到的最优方案weight数组:各个物品的重量value数组:每个物品的价值result:背包能装下的最大价值*/int[][] carry = new int[n+1][m+1];int[] weight = new int[n+1];int[] value = new int[n+1];//输入每个物品的重量、价值。for (int i = 1; i <= n; i++) {weight[i] = sc.nextInt();value[i] = sc.nextInt();}//按物品重量与背包容量升序，按照当前容量能装下当前物品的最大价值，// 更新carry数组（物品重量与背包容量向下兼容）。for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) {if (weight[i] > j)carry[i][j] = carry[i - 1][j];else {carry[i][j] = Math.max(carry[i - 1][j], value[i] + carry[i - 1][j - weight[i]]);}}}//输出最优解/*10 42 13 34 57 9*/for(int i=0; i<=n;i++){for(int j=0; j<=m;j++){System.out.print(carry[i][j]+" ");}System.out.println();}System.out.println("在背包容量为"+m+"的情况下，"+"所能装下物品的最大价值为："+carry[n][m]);}
}

代码运行结果：

0 0 0 0 0 0 0 0 0 0 0 
0 0 1 1 1 1 1 1 1 1 1 
0 0 1 3 3 4 4 4 4 4 4 
0 0 1 3 5 5 6 8 8 9 9 
0 0 1 3 5 5 6 9 9 10 12 
在背包容量为10的情况下，所能装下物品的最大价值为：12

时间复杂度：O（n^2）

1.2 基于贪心算法实现的部分背包问题

问题描述：对于每一个物品，可以选择放入物品全部或者物品的一部分，这种情况下选择物品的价值/物品的重量作为权重，按照权重将物品降序排序，首先放入权重最大的物品，直到不能完全放入一个物品，此时放入该物品的一部分。

贪心算法代码实现（Java）：

import java.util.Scanner;public class Package0fpart {
//创建物品类，包括物品重量、价值、是否全部放入背包、物品的权重(p=value/weight)public static class goods {int weight;int value;float n;float p;}public static void Greedy(goods[] a, int n, int v) {for (int i = 0; i < n; i++) {if (v > a[i].weight) { //当物品能放入背包时，将物品全部放入背包a[i].n = 1;v -= a[i].weight;} else if (v > 0) {//当物品无法全部放入背包时，放入一部分物品a[i].n = (float) v / a[i].weight;v = 0;}}}//插入排序算法实现物品排序public static void sort(goods[] arr) {if (arr.length >= 2) {for (int i = 1; i < arr.length; i++) {//挖出一个要用来插入的值，同时位置上留下一个可以存新的值的坑goods x = arr[i];int j = i - 1;//在前面有一个或连续多个值比x大的时候，一”直循环往前面找,将x插入到这串值前面while (j >= 0 && arr[j].p < x.p) {//当arr[j]比x小的时候，将j向后移一位，正好填到坑中arr[j + 1] = arr[i];j--;//将x插入到最前面arr[i + 1] = x;}}}}public static void main(String[] args) {Scanner sc = new Scanner(System.in);System.out.println("请输入物品数量及背包容量:");int n = sc.nextInt();int v = sc.nextInt();goods[] a = new goods[n]; //创建goods类数组并实例化for (int i = 0; i < n; i++)a[i] = new goods();for (int i = 0; i < n; i++) {System.out.println("请输入第" + (i + 1) + "个物品的重量及价值: ");a[i].weight = sc.nextInt();a[i].value = sc.nextInt();a[i].p = (float) a[i].value / a[i].weight;}sort(a);Greedy(a, n, v);int sumOfvalue = 0;int sumOfweight = 0;for (int i = 0; i < n; i++) {if (a[i].n == 0.0)break;sumOfweight += (a[i].weight * a[i].n);sumOfvalue += (a[i].value * a[i].n);System.out.println("装入背包的第" + (i + 1) + "个物品为: ");System.out.println("重量: " + a[i].weight + "价值:" + a[i].value + "完整 / 部分:" + a[i].n);System.out.println("背包装入的总价值: " + sumOfvalue);System.out.println("背包装入的总重量:" + sumOfweight);}}
}

程序运行结果：

请输入物品数量及背包容量:
3
50
请输入第1个物品的重量及价值: 
10
60
请输入第2个物品的重量及价值: 
20
100
请输入第3个物品的重量及价值: 
30
120
装入背包的第1个物品为: 
重量: 10 价值:60 完整 / 部分:1.0
背包装入的总价值: 60
背包装入的总重量:10
装入背包的第2个物品为: 
重量: 20 价值:100 完整 / 部分:1.0
背包装入的总价值: 160
背包装入的总重量:30
装入背包的第3个物品为: 
重量: 30 价值:120 完整 / 部分:0.6666667
背包装入的总价值: 240
背包装入的总重量:50进程已结束,退出代码0

时间复杂度：O（n）

1.3 基于动态规划实现的完全背包问题

问题描述：对于每一个物品，其数量是无限的，对于背包容量不同的情况下，对于同一个物品，考虑放入数量为k的不同价值情况（k=0、1、2...n），选择价值最大的放置情况更新最大价值数组，直到所有的物品均被选择过。

动态规划代码实现（Java）：

import java.util.Scanner;public class PackageofAll {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[][] f = new int[n + 1][m + 1]; // f数组表示物品数量为i、背包容量为j的情况下的最大价值int[] v = new int[n]; // n个物品的体积int[] w = new int[n]; // n个物品的价值int a = 0;while (sc.hasNextLine() && a != n) {v[a] = sc.nextInt();w[a] = sc.nextInt();a++;}for (int i = 1; i <= n; i++) {for (int j = 0; j <= m; j++) {for (int k = 0; k * v[i - 1] <= j; k++) {f[i][j] = f[i - 1][j]; // 当背包放不下当前物品时，f取不放入该物品时的最大价值if (j >= v[i - 1])     // 当背包能放下当前物品时，考虑不放入该物品与放入该物品之间的最大值f[i][j] = Math.max(f[i - 1][j], f[i - 1][j - k * v[i - 1]] + k * w[i - 1]);}}}for (int i = 0; i <= n; i++) {for (int j = 0; j <= m; j++) {System.out.print(f[i][j] + " ");}System.out.println();}System.out.println(f[n][m]); //f数组最后一位为所有情况下的最大价值，因为背包容量越大，背包容纳的价值也越大。}
}

程序运行结果：

3
4
1 15
3 20
4 30
0 0 0 0 0 
0 15 30 45 60 
0 15 30 45 60 
0 15 30 45 60 
60进程已结束,退出代码0

时间复杂度：O（n^3）

2 针对背包问题的动态规划算法优化

2.1 针对01背包问题的一维数组优化

问题描述：对于01背包问题，可以考虑将二维结果数组变为一维数组，数组下标表示背包容量，数组数值表示该背包容量下的最大价值，代码改进如下：

import java.util.Scanner;public class Packageof01 {public static void main(String[] args) {Scanner sc = new Scanner(System.in);//m为背包总容量，n为物品数量。int m = sc.nextInt();int n = sc.nextInt();/*carry数组:动态规划得到的最优方案weight数组:各个物品的重量value数组:每个物品的价值result:背包能装下的最大价值*/int[] carry = new int[m + 1];int[] weight = new int[n + 1];int[] value = new int[n + 1];//输入每个物品的重量、价值。for (int i = 1; i <= n; i++) {weight[i] = sc.nextInt();value[i] = sc.nextInt();}//按物品重量与背包容量升序，按照当前容量能装下当前物品的最大价值，// 更新carry数组（物品重量与背包容量向下兼容）。for (int i = 0; i <= n; i++) {for (int j = m; j >= weight[i]; j--) {// 背包容量逆序遍历，防止重复选取物品，j>=物品重量，过滤掉放不下的情况carry[j] = Math.max(carry[j], value[i] + carry[j - weight[i]]);}}for (int j = 0; j <= m; j++) {System.out.print(carry[j] + " ");}System.out.println();System.out.println("在背包容量为" + m + "的情况下，" + "所能装下物品的最大价值为：" + carry[m]);}
}

程序运行结果：

10 4
2 1
3 3
4 5
7 9
0 0 1 3 5 5 6 9 9 10 12 
在背包容量为10的情况下，所能装下物品的最大价值为：12进程已结束,退出代码0

时间复杂度：O（m*n）

2.2 针对完全背包问题的一维数组优化

与01背包问题类似，可以考虑用一维数组压缩空间，与01背包不同的是，完全背包的背包容量需要顺序遍历，用到当前物品的不同数量已经考虑过的情况。程序实现如下：

import java.util.Scanner;public class PackageofAll {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt();int m = sc.nextInt();int[] f = new int[m + 1]; // f数组表示物品数量为i、背包容量为j的情况下的最大价值int[] v = new int[n]; // n个物品的体积int[] w = new int[n]; // n个物品的价值int a = 0;while (sc.hasNextLine() && a != n) {v[a] = sc.nextInt();w[a] = sc.nextInt();a++;}for (int i = 1; i <= n; i++) {for (int j = v[i-1]; j <= m; j++) {// 背包容量从能放下物品开始遍历，降低时间复杂度f[j] = Math.max(f[j], f[j - v[i - 1]] + w[i - 1]);}}for (int j = 0; j <= m; j++) {System.out.print(f[j] + " ");}System.out.println();System.out.println(f[m]); //f数组最后一位为所有情况下的最大价值，因为背包容量越大，背包容纳的价值也越大。}
}

程序运行结果：

3
4
1 15
3 20
4 30
0 15 30 45 60 
60进程已结束,退出代码0

时间复杂度：可以看到，经过一维数组优化的算法，只需两次遍历就能求得最大价值，并且背包容量从能放下物品的容量开始遍历，所以总体时间复杂度为：O（m*n）