python - 动态规划 - 0-1背包问题
动态规划：
0-1背包问题，替换问题，解不唯一
找到最优子结构和重叠子问题，进而找到状态转移方程
最优子结构保证每个状态是最优的;
重叠子问题也即n状态的求法和n-1状态的求法是一样的；
实现上一般是根据状态转移方程自底向上的迭代求得最优解（也可以使用递归自顶向下求解）。
二维数组（状态转移矩阵）dp[i][j]来记录各个子问题的最优状态，其中dp[i][j]表示前i个物体面对容量j背包的最大价值。
最优解是在面对每个物体时选择能够最大化背包价值的状态。
0-1背包的状态转移方程为
f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }
----------
输入：两个数列，长度为N，一个是重量，一个是对应的单价；每种物品只能选择0个或1个。
输出：在限定的总重量范围内，得出最大的价格组合，将选中的物品放入背包，没选中的丢弃。
例：
ID：[0,1,2,3,4,5]
重量：[5,4,6,3,2,1]
单价：[1,2,100,3,4,5]
限定重量：9
最优组合：重量[3,2,1]总价格5+8+9=22
重量[6,2,1]总价格600+8+5
---------
直观上的解法是：先挑选一个装包里，再装下一个：
这就是贪婪算法。先按照一定的规则排序，比如按重量、按价格，按密度等，然后从大到小依次选取。
贪婪算法：得到的是局部最优解，不一定是全局最优解。但效率更高，简单。实际应用很多采用该方法。
如果满足条件，就把下一个也装进包里；
如果不满足条件：
丢弃下一个
将下一个与包里的融合进行比较，得出包里新的组合（通过二维数组来展示）
以下这样的实现太难了，找不到程序的着力点：
for i=1到N
if 背包剩余容量 > 第i个的重量：
第i次的总价格 = 第i-1次的总价格 + 第i个的价格
背包剩余容量 = 背包剩余容量 - 第i个的重量
else
第i次的总价格 = 第i-1次的总价格
--------------
实际实现是这样的：
动态规划算法：得到的是最优解。但比较复杂，需要得到状态转移方程。
For row=N-0 反向查找
选取这一行第一次出现最大值的列数COL
将最大值与上一行比较
若相等，该行对应的物品不是选中的物品，列数不变，行数减一
若不相等，记录该行对应的物品，列数-cost(row)，行数减一
形成可递归的矩阵：
新行数 = 行数减一
新列数 = COL-1 或 COL -1- cost(row)
递归结束的条件为查找当前递归矩阵的最大值为零。
---------
拓展：
分组背包：
有N件物品和一个容量为V的背包。第i件物品的费用是c，价值是w。
这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。
求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。
依赖问题：
这种背包问题的物品间存在某种“依赖”的关系。也就是说，i依赖于j，表示若选物品i，则必须选物品j。
为了简化起见，我们先设没有某个物品既依赖于别的物品，又被别的物品所依赖；
另外，没有某件物品同时依赖多件物品。
---------
-------
源代码：
# encoding:utf-8 import os def bag(weight,cost,max_cost): '''f(i,v) = max{ f(i-1,v), f(i-1,v-c[i])+w[i] }''' n = len(cost) res=[[0 for j in range(max_cost+1)] for i in range(n+1)] for i in range(1,n+1): # 物品的id（0-n） for j in range(1,max_cost+1): # 总容量（一个变化着的量） res[i][j]=res[i-1][j] if j>=cost[i-1] and res[i][j] < (res[i-1][j-cost[i-1]] + weight[i-1]): res[i][j] = res[i-1][j-cost[i-1]] + weight[i-1] row, col = show_res(res) return res, res[row][col] def show_res(res): row = len(res) for i in range(0,row,1): col = len(res[i]) print for j in range(0,col,1): print res[i][j], print return row-1, col-1 def show_result(res, cost): '''从结果往前查找，找到第0列结束''' global res_id row, col = show_res(res) result = res[row][col] # 递归结束的条件为查找当前递归矩阵的最大值为零 if result == 0: return 0 row0 = 0 col0 = 0 for i in range(col,0,-1): if result != res[row][i]: #选取这一行第一次出现最大值的列数COL col0 = i+1 # 将最大值与上一行比较 if res[row][i+1] != res[row-1][i+1]: # 若不相等，记录该行对应的物品，列数-cost(row)，行数减一 # print 'cost', row, cost[row-1] col0 = col0 - cost[row-1] res_id.append(cost[row-1]) else: # 若相等，该行对应的物品不是选中的物品，列数不变，行数减一 pass break # 形成可递归的矩阵： # 新行数 = 行数减一 # 新列数 = COL - 1 或 COL - cost(row) - 1 row_new = row - 1 col_new = col0 - 1 # print row_new, col_new res0 = [] for i in range(0,row_new+1,1): res0.append([0]) # 先创建i行 for j in range(0,col_new+1,1): res0[i].append(int(res[i][j+1])) # 对每行中的数赋值，注意不是res0[i].append(int(res[i][j]))，因为已经有了第一列 # show_res(res0) return show_result(res0, cost) if __name__=='__main__': max_cost = 10 # cost=[2,2,6,5,4] # max_cost = 10 result = [4,2,2] # weight=[6,3,5,4,6] cost = [5,4,6,3,2,1] # max_cost = 10 result = [6,2,1] weight = [1,2,100,3,4,5] # cost = [10,3,4,5] # max_cost = 10 result = [5,4] # weight = [3,4,6,7] res_id = [] res, max_weight = bag(weight,cost,max_cost) res0 = show_result(res, cost) # res1 = show_result(res0, cost) # res2 = show_result(res1, cost) # res3 = show_result(res2, cost) # res4 = show_result(res3, cost) print '符合最大cost限制 %d 的cost取值为' % max_cost, res_id, '\nweight最大为 %d' % max_weight ''' 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 3 3 0 0 0 0 2 2 100 100 100 100 102 0 0 0 3 3 3 100 100 100 103 103 0 0 4 4 4 7 100 100 104 104 104 0 5 5 9 9 9 100 105 105 109 109 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 0 0 0 2 2 2 2 2 3 3 0 0 0 0 2 2 100 100 100 100 102 0 0 0 3 3 3 100 100 100 103 103 0 0 4 4 4 7 100 100 104 104 104 0 5 5 9 9 9 100 105 105 109 109 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 0 0 0 2 2 2 2 2 0 0 0 0 2 2 100 100 100 0 0 0 3 3 3 100 100 100 0 0 4 4 4 7 100 100 104 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 2 2 2 0 0 0 0 2 2 100 0 0 0 3 3 3 100 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 0 0 2 2 2 0 0 0 0 2 2 100 0 0 0 符合最大cost限制 10 的cost取值为 [1, 2, 6] weight最大为 109 '''