首页 > 代码库 > 10.动态规划（3）——0-1背包问题
10.动态规划（3）——0-1背包问题
在上一篇《9.动态规划（2）——子集和问题》中，谈到了什么是子集和问题，以及实现。背包问题实际也是子集和问题的一种，不过背包问题不是“判断问题”而是一个“最优问题”。而背包问题实际上又分为“0-1背包”，“完全背包”，本文对“0-1背包”进行讲解。
问题：有n个物品，每个物品的重量为weigh[i]，每个物品所对应的价值为price[i]，现在有一个背包，背包所能承受的重量为W，问背包能装下的物品总价值最大是多少？
定义s[i, j]表示前i个物品的总价值，j为背包的承重量。当j = W或者最接近于W且小于W时，此时就是问题的解。
对于“动态规划”的关键就是要找到其递推公式，递推公式往往会将一个问题以某个值为边界拆分为两部分。背包问题的求解是子集和问题的最优化求解，在《9.动态规划（2）——子集和问题》中分析过递推公式的推导工程，在这里重新分析推导。
分析：s[i, j]表示前i个物品，如果前i - 1个物品价值已经达到背包承重量j的极限，那么第i个物品就不能放进去(j - wi < 0)，此时就可表示s[i, j] = s[i - 1, j]。但如果第i - 1个物品未达到背包承重量j的极限(j - wi >= 0)，此时我们计算前i - 1个物品的价值就是s[i - 1, j - wi]，此时加上第i个物品的价值就可以表示为s[i - 1, j - wi] + pi。
综上得到递推公式：
举例：物品的重量集合w = (2, 4, 1, 5, 3)，物品的价格集合 p = (4, 5, 19, 3, 2)，背包重量6。通过上面的递推公式，将这个背包问题利用矩阵来表示，第6列的最大值即为背包重量为6时的最大价值。
Java
1 package com.algorithm.dynamicprogramming; 2 3 import java.util.Arrays; 4 5 /** 6 * 0-1背包问题 7 * | s[i - 1, j] (j - wi < 0) 8 * s[i, j] = | | s[i - 1, j] 9 * | Max | (j - wi >= 0)10 * | | s[i - 1, j -wi] + pi11 * Created by yulinfeng on 7/3/17.12 */13 public class KnapsackProblem {14 public static void main(String[] args) {15 int[] weight = {2, 4, 1, 5, 2};16 int[] price = {4, 5, 19, 3, 2};17 int knapsackWeight = 6;18 int value =http://www.mamicode.com/ knapsackProblem(weight, price, knapsackWeight);19 System.out.println(value);20 }21 22 /**23 * 动态规划求解0-1背包问题24 * @param weight 物品重量25 * @param price 物品价值26 * @param knapsackWeight 背包承重量27 * @return28 */29 private static int knapsackProblem(int[] weight, int[] price, int knapsackWeight) {30 int row = weight.length + 1;31 int col = knapsackWeight + 1;32 int[][] solutionMatrix = new int[row][col];33 int[] values = new int[row];34 values[0] = 0;35 for (int i = 0; i < row; i++) {36 solutionMatrix[i][0] = 0;37 }38 for (int j = 0; j < col; j++) {39 solutionMatrix[0][j] = 0;40 }41 42 for (int i = 1; i < row; i++) {43 for (int j = 1; j < col; j++) {44 solutionMatrix[i][j] = solutionMatrix[i - 1][j];45 if (j - weight[i - 1] >= 0 && solutionMatrix[i - 1][j - weight[i - 1]] + price[i - 1] > solutionMatrix[i][j]) {46 solutionMatrix[i][j] = solutionMatrix[i - 1][j - weight[i - 1]] + price[i - 1];47 }48 }49 values[i] = solutionMatrix[i][col - 1];50 }51 Arrays.sort(values);52 return values[values.length - 1];53 }54 }
Python3
1 def knapsack_problem(weight, price, knapsackWeight): 2 ‘‘‘ 3 0-1背包问题 4 | s[i - 1, j] (j - wi < 0) 5 s[i, j] = | | s[i - 1, j] 6 | Max | (j - wi >= 0) 7 | | s[i - 1, j -wi] + pi 8 9 Created by yulinfeng on 7/3/17.10 ‘‘‘11 row = len(weight) + 112 col = len(price) + 113 solutionMatrix = [[0 for c in range(col)] for r in range(row)]14 values = [0] * row15 for i in range(row):16 solutionMatrix[0][i] = 017 for j in range(col):18 solutionMatrix[j][0] = 019 for m in range(1, row):20 for n in range(1, col):21 solutionMatrix[m][n] = solutionMatrix[m - 1][n]22 if n - weight[m - 1] >= 0 and solutionMatrix[m - 1][n - weight[m - 1]] + price[m - 1] > solutionMatrix[m][n]:23 solutionMatrix[m][n] = solutionMatrix[m - 1][n - weight[m - 1]] + price[m - 1]24 values[m] = solutionMatrix[m][col - 1]25 26 values.sort()27 return values[len(values) - 1]28 29 weight = (2, 4, 1, 5, 2)30 price = (4, 5, 19, 3, 2)31 knapsackWeight = 632 value =http://www.mamicode.com/ knapsack_problem(weight, price, knapsackWeight)33 print(value)
10.动态规划（3）——0-1背包问题