【最全面详细解释】背包问题详解
一、背包问题
背包问题: 一个背包最多可放重量为weight的物品,现在有n件物品的集合S,物品的重量分别为[w0,w1,w2,w3…w n-1]. 问题是能够从这n件物品中取出若干件物品刚好装满这个背包,不考虑背包的容积,只考虑重量,检查这个问题是否有解,有解就输出Yes,没有则输出No.
二、解法一
1.思路
解题思路: 先假设weight>=0,n >=0, knap(weight,n)表示n件物品相对于总重量weight的背包问题。我们现在只考虑这个物品是否有解的情况下,通过考虑一件物品的 选或者不选,我们把问题划分成下面两种情况:
如果不选最后一件物品(其重量为w n-1),那么 knap(weight,n-1)的解就是 knap(weight,n)的解,如果找到了前面一个子问题的解,也就找到了后面的问题的解。
如果要选最后一件物品,那么knap(weight-Wn-1,n-1)有解的话,这个问题的解加上最后一个物品的重量就是knap(weight,n)的解,也是将一个问题转化成了一个稍小规模的问题。
注意:每件物品只有一件,用了就没有了。
我们利用这个函数knap()一个将问题转化为更小规模的问题。一直这样下去,我们可以归结为下面几种情况。
1、当weight已经等于0了,这说明问题有解。 2、在不断递归的情况下,weight小于0,这说明我们不断递归下去是没有解的。 3、重量weight还大于0,但是已经没有物品可用了,我们每次递归都有可能会确认某一个物品是不是可选的,也就是说每次递归物品都在被消耗,当物品被消耗完了,重量还大于0,这说明没有解。
def knap_rec(weight,wlist,n): if weight == 0: return True if weight < 0 or (weight > 0 and n < 1): return False if knap_rec(weight - wlist[n-1],wlist,n-1): # print("Item " + str(n) + ":",wlist[n-1]) return True if knap_rec(weight,wlist,n-1): return True else: return False weight = 16 wlist = [2,3,4,10,20,25] n = 6 if __name__ =="__main__": if knap_rec(weight,wlist,n): print("YES") else: print("NO")
三、解法二
1.思路
第二个解题思路: 我们直接枚举所有的可能性,当枚举到符合条件的事件时,就跳出枚举循环。
这里我们要借用内置的combinations函数,
更多更详细的combinations用法参考大佬文章。
from itertools import combinations def func(weight,wlist,n): for i in range(1,n+1): datas = combinations(wlist,i) for data in datas: if sum(data) == weight: print("YES") return print("NO") return func(weight,wlist,n)