最近碰到很多有关于动态规划的问题，总结一下：

一、01背包问题（python实现）

例：给定3个物品，背包的容量为50磅

物品1重10磅，价值60；物品2重20磅，价值100；物品3重30磅，价值120

求背包能装下的最大价值

求解表如下

物品    0磅       10磅        20磅        30磅        40磅         50磅

 0     0价值     0价值       0价值       0价值      0价值        0价值

 1      0价值    60价值     60价值      60价值    60价值      60价值

 2     0价值     60价值    100价值    160价值    160价值    160价值

 3     0价值     60价值    100价值    160价值    180价值    220价值

由上表可知最大容量的最大价值是220

代码如下：

1 def weight_goods(n, weight, w, v): 2     #n是物品数 3     #weight是背包容量 4     #w列表是每个物品的体积 5     #v列表是每个物品的价值 6  7     #res1 = [[0 for j in range(weight+1)] for I in range(n+1)]   一步实现 8     #三种物品选入背包的重量对应的价值res[i]是,物品res[i][j]是选入物品的价值，用0初始化二维数组 9     res = []10     for I in range(n+1):11         for j in range(weight+2):12             a = [0]*j13         res.append(a)14     15     #当分别放入0，1，2，3物品的组合时，输出容量为0-50磅的价值16     for I in range(1, n+1):17         for j in range(0, weight+1):18             res[i][j] = res[i-1][j]19     20     #以下是状态转移方程：res[i][j] = max{res[i-1][j-w[i-1]]+v[i-1], res[i][j]}21     if j >= w[i-1] and res[i][j] < res[i-1][j-w[i-1]]+v[i-1]:22         res[i][j] = res[i-1][j-w[i-1]]+v[i-1]23 24     #以上得出背包最大容量下的最大价值是res[n][weight],以下通过排列组合得出所有可能组合的价值值25     #然后在判断容量不超过背包容量的情况下，过滤出与已知最大价值的值相等的组合，此组合就是装入背包的物品26     import itertools27     for i in range(len(w)+1):28         h = list(itertools.combinations(range(1, len(w)+1), i))29         for j in h:30             x = []31             y = []32             for z in j:33                 x.append(v[z-1])34                 y.append(w[z-1])35             if sum(x) == res[n][weight] and sum(y) <= 50;36                 for z in j:37                     print('第', z, '个物品,', end='' )38       print('得到的最大价值=', res[n][weight])39 40 weight_goods(3, 50, [10,20,30], [60,100,120])

 

下一章节：完全背包