背包问题及其变型(python)

56 阅读 0 评论 37 点赞

我是靠谱客的博主温暖棒球，最近开发中收集的这篇文章主要介绍背包问题及其变型(python)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

1. 0，1问题

一个背包，往里装东西，重量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]

2 背包问题变形：完全背包问题

还是原来的问题，上次是每个物体只能用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]

3 变形：多重背包问题，给定数量的物体，第一个是1个物体，第二个是无限物体，这个是介于之间，给定物体数目

方法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]

4 背包问题变形：混合背包问题

物品一共有三类：

第一类物品只能用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])

5 背包问题变形：分组背包问题

分组，组内只能选择一个

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])