今天做笔试题，看到一个用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实现
'''
0-1背包问题
'''
def backpag_dynamic(w, v, container, res):
assert len(w) == len(v),
"weight和value的尺度不同！"
limits = container +
1
n = len(w)
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
n =
5
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()
