[most comprehensive and detailed explanation] detailed explanation of knapsack problem

---

One 、 knapsack problem

knapsack problem ：
The maximum weight of a backpack is weight The items , Now there is n A collection of items S, The weights of the articles are [w0,w1,w2,w3…w n-1].
The problem is to be able to n Take several items out of the items to fill the backpack , Regardless of the volume of the backpack , Weight only , Check whether the problem is solved , If there is a solution, output Yes, If not, output No.

Two 、 Solution 1

1. Ideas

Their thinking ：
To assume that weight>=0,n >=0, knap(weight,n) Express n Items relative to total weight weight The knapsack problem of . Now we only consider whether the object has a solution , By considering the
Choose or not , We divide the problem into the following two cases ：

If you don't choose the last item （ Its weight is w n-1）, that knap(weight,n-1) The solution is knap(weight,n) Solution , If we find the solution of the previous subproblem , So we can find the solution of the following problem .

If you want to choose the last item , that knap(weight-Wn-1,n-1) If there is a solution , The solution of this problem plus the weight of the last object is knap(weight,n) Solution , It also turns a problem into a smaller one .

Be careful ： There is only one item per item , If you use it, you won't have it .

We use this function knap() A problem that translates into a smaller problem . All the time , We can boil it down to the following situations .

1、 When weight Already equal to 0 了 , This shows that the problem has a solution .
2、 In the case of constant recursion ,weight Less than 0, This shows that there is no solution if we recurse continuously .
3、 weight weight Greater than 0, But there are no more items available , Every time we recurse, it is possible to confirm whether an item is optional , That is, each recursive item is consumed , When items are consumed , Weight is greater than 0, This shows that there is no solution .

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

3、 ... and 、 Solution 2

1. Ideas

The second problem-solving idea ：
Let's just enumerate all the possibilities , When enumerating events that meet the criteria , Just jump out of the enumeration loop .

Here we want to borrow the built-in combinations function ,

More in detail combinations For usage, refer to the article of the boss .Python Use combinations Realize permutation and combination

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)