0-1背包问题

今天做笔试题，看到一个用0-1背包解决的问题。

什么是背包问题？

背包问题，常见的有三种类型：基本的0-1背包、完全背包和多重背包、二维背包等。

首先是基本的0-1背包问题。因为这里的物品一般指花瓶、玉器什么的，要么拿、要么不拿，只有0和1两种状态，所以也叫0-1背包。0-1背包虽然简单，却很重要，是“万法之源”，是其他几类问题的基础。

初学者有时会认为，0-1背包可以这样求解：计算每个物品的Vi/Wi，然后依据Vi/Wi的值，对所有的物品从大到小进行排序。其实这种贪心方法是错误的。就像典型DP问题中的硬币问题（给定一定面额的硬币，让凑到某数所需最小的钱数）

动态规划

其实，0-1背包是DP的一个经典实例，可以用动态规划求解。

DP求解过程可以这样理解：对于前i件物品，背包剩余容量为j时，所取得的最大价值（此时称为状态3）只依赖于两个状态。

状态1：前i-1件物品，背包剩余容量为j。在该状态下，只要不选第i个物品，就可以转换到状态3。

状态2：前i-1件物品，背包剩余容量为j-w[i]。在该状态下，选第i个物品，也可以转换到状态3。

因为，这里要求最大价值，所以只要从状态1和状态2中选择最大价值较大的一个即可。

状态转换方程：

dp(i,j)=Max(dp(i−1,j),dp(i−1,j−w[i])+v[i])

dp(i,j) 表示前i件物品，背包剩余容量为j时，所取得的最大价值。

python实现

# -*- coding:utf-8 -*-
# author: Gao Daiheng
''' 0-1背包问题 '''

def backpag_dynamic(w, v, container, res):
    assert len(w) == len(v), "weight和value的尺度不同！"

    limits = container + 1
    n = len(w)  # n为6
    # c[i][j]表示在前i个物体中，能够装入载重量为j的背包中的物体的最大价值
    c = [[0 for j in range(limits)] for i in range(n)]

    for i in range(1, n):
        for j in range(limits):

            c[i][j] = c[i - 1][j]

            if j >= w[i] and (c[i-1][j-w[i]] + v[i]) > c[i][j]:
                c[i][j] = c[i-1][j-w[i]] + v[i]
    # 抽取位置
    for i in range(n-1, 0, -1):
        if c[i][j] > c[i - 1][j]:
            res[i] = True
            j -= w[i]

    return max(c[-1])


def main():
    C = 10  # 容量为10
    n = 5  # 物品为5个
    # 注意，务必要在v(值) 和 w(重量)前面分别加上
    # 0，即子问题的形式从0开始
    v = [0, 2, 4, 3, 6, 8]
    w = [0, 1, 5, 3, 4, 5]
    res = [False for i in range(n + 1)]
    maxv = backpag_dynamic(w, v, C, res)
    print('最大值为：{}'.format(maxv))
    for i in range(len(res)):
        if res[i]:
            print("第{}位被抽出".format(i))

if __name__ == "__main__":
    main()