首页 > 代码库 > 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

  综上得到递推公式:

技术分享

  举例:物品的重量集合= (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背包问题