Complete knapsack problem (template)

Summary of problems

 There's a backpack , The maximum bearing capacity is N, Now we need to pack some items i（ The value of the item is value[i], The weight of the article is weight[i]）, There is no limit to the number of items （ That is, it can be installed repeatedly ）, Ask for the maximum value of these items packed on this back .

Complete backpack features

 Each item has an infinite number of 

Completely backpack （ One dimensional rolling array version ）

analysis

• Ahead 01 Backpack we can know , Items circulating outside are in positive order , Internal reverse circulation backpack . Internal reverse circulation is to ensure that items can only be added once , But the complete backpack has infinite items , It shows that my backpack can traverse forward , There is nothing wrong with the superposition of sub problems .
• 01 2D in backpack dp Two of the arrays for The order of traversal can be reversed , A one-dimensional dp Two of the arrays for The sequence of the cycle must first traverse the items , Then traverse the backpack capacity .
• In a complete backpack , For one dimension dp Array , In fact, two for The nesting order of loops can be reversed
• therefore , Whether it's 01 Backpack or full backpack , We usually go through items first , And then traverse the backpack , Be careful ： Here is general

Code

#  Completely backpack （ One dimensional rolling array version ）

weight =[1,3,4]
value = [15,20,30] 
Max = 4 #  The maximum capacity of the backpack 

dp = [0]*5 # dp[j] Indicates that the backpack capacity is j The maximum value of is dp[j]

for i in range(3):
    for j in range(weight[i],5):
        dp[j] = max(dp[j],dp[j-weight[i]]+value[i])
print(dp)

The final results

So the capacity is 4 The backpack , The greatest value is 60

If there is a mistake , Please correct me , Welcome to exchange , thank you *(･ω･)ﾉ