0-1背包问题(动态规划java实现)

0-1背包问题(动态规划java实现)

背包问题:

我们有一个背包:背包容量为C,先存在若干个物品:每个物品i有自己的重量W[i],也有自己的价值V[i];现在需要讨论在现有背包容量不溢出的情况下,每一个物品只能放入背包一次(0-1背包问题),计算出最后背包能达到的最大价值,同时输出里面所存放那些物品; 我们利用动态规划进行分析时,需要将这个大问题拆成小问题进行处理:此时我们假设添加第i(i从0到n[n为存在物品的总个数])个物品,当前容量为j(就从0到C[C为背包的容量])时所能达到的最大价值maxVal[i][j];

故我们定义一个二维数组int[][] maxVal = new int[n + 1][C + 1];其中n为物品的个数,C为背包的容量 此处:我们举例假设背包的容量为5,现存在4件物品: 笔记本:重量1,价值1500; 钢笔:重量1,价值1000; 书本:重量2,价值2000; 水杯:重量3,价值3000 故我们定义int[][] maxVal = new int[5][6]

填表进行背包问题的分析

行(i):表示当添加的第i个物品,j(重量):表示此时背包的容量为j (1)当我们放入第i个物品(i = 0),或者我们背包当前总容量(j=0)时,此时背包中的总价值应当为0; (2)当我们放入第i个物品(i > 0),且当前背包容量(j > 0)时: 2.1如果此时放入的第i个物品的重量已经超过了当前背包的容量:W[i] > j 则说明这个物品无法放入背包,故此时的背包的最大价值maxVal[i][j] = maxVal[i-1][j],即为背包容量为j的情况下, 存放上一个物品时的最大容量 2.2如果此时放入的第i个物品的重量小于或者等于当前背包的容量:W[i] <= j 则说明此时这个物品可以放入: 此时存在两个情况: 第一种是val1 = maxVal[i - 1][j]:背包容量为j的情况下,存放上一个物品时的最大容量 第二种是val2 = V[i] + maxVal[i - 1][j - W[i]]:即当前物品的价值+当前背包容量(j)去除当前物品重量(W[i])以后的最大价值 所以此时的最大价值为两者的最大值 maxVal = Math.max(maxVal[i - 1][j],V[i] + maxVal[i - 1][j - W[i]]); 我们按照上述规律填表得到:

java代码实现

package com.bingym.dynamicprogramming; import java.util.Arrays; import java.util.LinkedList; import java.util.List; import java.util.Stack; public class KnapsackProblem { public static void main(String[] args) { //定义物品的价值 int[] V = {1500,1000,2000,3000}; //定义物品对应的重量 int[] W = {1,1,2,3}; //定义背包的重量 int C = 5; //定义一个二维数组:存放遍历到第i个物品,背包容量为j时的背包最大价值 int n = W.length;//物品的个数 int[][] maxVal = new int[n + 1][C + 1]; //List<Integer> pathList = new LinkedList<>(); int[][] path = new int[n + 1][C + 1];//保存获取最大价值时添加的物品 //进行背包问题的处理 //1.当我们放入第i个物品(i = 0),或者我们背包当前总容量(j=0)时,此时背包中的总价值应当为0; for (int i = 0; i < maxVal.length; i++) { maxVal[i][0] = 0;//将第一列置0 } for (int i = 0; i < maxVal[0].length; i++) { maxVal[0][i] = 0;//将第一行置0 } //2.当我们放入第i个物品(i > 0),且当前背包容量(j > 0)时: for (int i = 1; i <= n; i++) {//从第1个物品到第n个物品(n = maxVal.length - 1) for (int j = 1; j <= C; j++) {//背包当前容量从1到C(C = maxVal[i].length - 1) if (W[i-1] > j) {//由于第一个物品在数组中的索引为0开始,所以此处W[i] -> W[i-1] //2.1如果此时放入的第i个物品的重量已经超过了当前背包的容量 maxVal[i][j] = maxVal[i - 1][j]; }else { //2.2如果此时放入的第i个物品的重量小于或者等于当前背包的容量 //由于第一个物品在数组中的索引为0开始,所以此处W[i] -> W[i-1],V[i] -> V[i - 1] //maxVal[i][j] = Math.max(maxVal[i - 1][j],V[i - 1] + maxVal[i -1][j - W[i - 1]]); if (maxVal[i - 1][j] <= V[i - 1] + maxVal[i -1][j - W[i - 1]]) { maxVal[i][j] = V[i - 1] + maxVal[i -1][j - W[i - 1]]; path[i][j] = 1; }else { maxVal[i][j] = maxVal[i - 1][j]; } } } } /*for (int i = 0; i < maxVal.length; i++) { for (int j = 0; j < maxVal[i].length; j++) { System.out.print(maxVal[i][j] + " "); } System.out.println(); }*/ //输出背包问题的最大价值 System.out.println("该背包获取的最大价值为:" + maxVal[n][C]); //获取背包最大价值的放入物品的方式 int row = path.length - 1; //行的最大下标 int col = path[0].length - 1; //列的最大下标 Stack<Integer> pathStack = new Stack<>(); while(row > 0 && col > 0 ) { //从path的最后开始找 if(path[row][col] == 1) { pathStack.push(row); col = col - W[row-1]; //w[i-1] } row--; } System.out.println("其中背包获取最大价值时,存放的物品为:"); while (!pathStack.isEmpty()) { int index = pathStack.pop(); System.out.printf("将第%d个商品放入到背包\n", index); } } }