python Solution to Knapsack Problem Based on Recursion

Recursion is a good thing, and any problem with recursive nature becomes very simple through recursive function calls. A very complicated problem can be solved in a few lines of code.

The simplest recursive question: There are several items with weights of W1, W2... Wn in the existing package with weight of weight. Can you select several items with weight of weight?

How weight is specifically composed has the following two situations (assuming that when Wn is selected, it is just enough for weight):

1. weight is sufficient from Wn-1, then weight=W1+W2 + ....+Wn=W1+W2 + ....+Wn-1.

2. Adding Wn is just enough for weight, which naturally has weight=W1+W2 + ....+Wn.

If one of the above two cases has a solution, then the problem has a solution, so we can remove Wi from the backpack and go back to see the value of weight.

After a series of backward deduction, the value of weight has the following three situations:

1. weight is just equal to 0//, indicating that there is a solution

2. weight < 0//Impossible, so there is no solution

3. weight > 0 and without W//Impossible, no solution

 def knap(weight,weights,n): //weight Is the capacity of the package, weights Yes 1 A table of all weights, n Quantity by weight 
    if weight==0:
     return True;
    if weight<0 or (n<1 and weight>0):
     return False;
    if knap(weight-weights[n-1],weights,n-1): // Situation  2
     print(weights[n-1])
     return True
    if knap(weight,weights,n-1): // Situation  1
     return True
    else:
     return False

Super simple! ! ! If dynamic programming is used to solve the problem, a few 10 lines of code should be used. This is 12 lines of code, simple and clear! ! !