一个背包，往里装东西，重量w(weight)分别为为[2,3,4,5] 价值v(value)对应为[3,4,5,6] 如果你的容量为8,每个物品只有一个，求你能装入背包的最大价值
我们可以一步一步来 ，先创建一个表格 (数组), 数组dp[i][j] i代表你只用前i个物体，j代表你的剩余容量，dp[i][j] 代表在此情况下可以得到的最大价值，先得到一个表格
先填第一行(也就是假设现在你只有第一个物体), 首先第一个物体重量为2 剩余容量为1，剩余容量小于物体重量，则最大价值为0， 第二个数剩余容量=物体容量，可以拿 填上第一个物体的价值3 就这样填上第一行 ， 继续填第二行 第二行代表的意义就是我们现在可以使用的有两个物体了，使用这两个物体能够得到的最大价值。这一共可以分为两种情况，一种是放第二个物体，一种是不放第二个物体，选择其中大的，转移方程为dp[i][j] = max(dp[ i - 1, j ], dp[ i - 1, j - w[ i ] ] + v [ i ] ) 这里解释下放第二个物体的式子，dp[ i-1, j - w[ i ] ]代表你把第二个物体的容量空出来时，能得到的最大价值， 再加上这个物体的价值。就这样填好所有的。
则 表格中最后一个物体就是面对所有物体，剩余容量为C时能得到的最大价值了。
def pack1(w, v, C): #每个东西只能选择一次 dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)] for i in range(1, len(w)+1): for j in range(1, C+1): if j < w[i-1]: #如果剩余容量不够新来的物体 直接等于之前的 dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]]+ v[i-1]) return dp[len(w)][c]这个是得到的dp结果
观察发现，可以对它的空间复杂度进行优化，我们可以用一维数组只保存最后一行, 代码如下
def pack1(w, v, c): #它是先得到第一行的值，存到dp中，然后再直接用dp相当于就是上一行的值，所以下面必须用逆序 #否则dp[j-w[i-1]]可能会用到你本行的值，从大到小就不会 dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)):#这里必须用逆序 if w[i-1] <= j: dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1]) return dp[c]还是原来的问题，上次是每个物体只能用1次，现在改成无限次，转移方程只需要修改一点即可dp[i][j] = max(dp[ i - 1, j ], dp[ i, j - w[ i ] ] + v [ i ] ) 只需要把后面的i-1 -> i 即可
def pack2(w, v, C): #每个东西能选择多次 完全背包问题 dp = [[0 for _ in range(C+1)] for _ in range(len(w)+1)] for i in range(1, len(w)+1): for j in range(1, C+1): if j < w[i-1]: dp[i][j] = dp[i-1][j] else: dp[i][j] = max(dp[i-1][j], dp[i][j-w[i-1]]+ v[i-1]) for i in dp: print(i) pack2([2,3,4,5], [3,4,5,6], 8)结果为
[0, 0, 0, 0, 0, 0, 0, 0, 0] [0, 0, 3, 3, 6, 6, 9, 9, 12] [0, 0, 3, 4, 6, 7, 9, 10, 12] [0, 0, 3, 4, 6, 7, 9, 10, 12] [0, 0, 3, 4, 6, 7, 9, 10, 12]同样可以优化空间复杂度 ，只需要把逆序改成顺序 即可。
def pack2(w, v, C): dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in (range(1, c+1)): if w[i-1] <= j: dp[j] = max(dp[j], dp[j-w[i-1]]+v[i-1]) return dp[c]方法1：再多加个循环试一下k个物体的价值, 这次直接上优化完的一维数组的
def pack3(w, v, s, c): dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)): for k in range(s[i-1] + 1): if k*w[i-1] <= j: dp[j] = max(dp[j], dp[j-k*w[i-1]]+k*v[i-1]) return dp[c]方法2：想象加入物体数量为4个我们直接在 w= [2,3,4,5] v = [3,4,5,6] s(个数)=[1,1,1,3] 如果我们直接把4个物体分成3个1个物体，就可以直接转变成0，1问题 。 w变成[2,3,4,5,5,5], v变成[3,4,5,6,6,6] 这就完全变成了0，1问题。 但是如果物体个数太多这样复杂度 高，我们有更好的划分方法。 比如13 我们可以划分为1+2+4+6，利用这个划分，原来需要划分为n个1，现在只需要log n 个组 了
def pack3(w, v, s, c): for i in range(len(s)): k = 1 s_value = s[i] while k<=s_value: w2.append(k*w[i]) v2.append(k*v[i]) s_value -= k k *= 2 if s_value>0: w2.append(s_value*w[i]) v2.append(s_value*v[i]) #前面是划分，后面是0，1背包 dp = [0 for _ in range(c+1)] for i in range(1, len(w2)+1): for j in reversed(range(1, c+1)): if w2[i-1] <= j: dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) return dp[c]物品一共有三类：
第一类物品只能用1次（01背包）；第二类物品可以用无限次（完全背包）；第三类物品最多只能用 sisi 次（多重背包）；si=−1 表示第 ii 种物品只能用1次；si=0 表示第 ii 种物品可以用无限次；si>0 表示第 ii 种物品可以使用 si 次； def pack4(w, v, c, s): w2 = [] v2 = [] s2 = [] for i in range(len(s)): if s[i] == 0 or s[i] == -1: w2.append(w[i]) v2.append(v[i]) s2.append(s[i]) else: s_value = s[i] k = 1 while k <= s_value: w2.append(k*w[i]) v2.append(k*v[i]) s2.append(s[i]) s_value -= k k *= 2 if s_value> 0: w2.append(s_value*w[i]) v2.append(s_value*v[i]) s2.append(s[i]) #上面把si>0的背包拆分了（变成0，1背包）下面分成0，1背包和无限背包两种 dp = [0 for _ in range(c+1)] for i in range(1, len(w2)+1): if s2[i-1] == 0: for j in (range(1, c+1)): if j-w2[i-1]>=0: dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) else: # print('i',i) for j in reversed(range(1, c+1)): if j-w2[i-1]>=0: # print('k', k) dp[j] = max(dp[j], dp[j-w2[i-1]]+v2[i-1]) # print('dp['+str(j)+']', dp[j]) # print(dp) print(dp[c])分组，组内只能选择一个
def pack5(w, v, n, c): """ w: list[list, list,...] v: list[list, list,...] n:list 组内的长度 """ dp = [0 for _ in range(c+1)] for i in range(1, len(w)+1): for j in reversed(range(1, c+1)): for k in range(n_list[i-1]): #别的和0，1背包一样 就是这里枚举一下每个组内的值，在每个组内选出一个max值 if j-w[i-1][k] >= 0: # print(dp[j]) dp[j] = max(dp[j], dp[j-w[i-1][k]] + v[i-1][k]) # print(dp) print(dp[c])在重量的基础上再加上一个体积约束
