当前位置:网站首页>Why should a complete knapsack be traversed in sequence? Briefly explain

Why should a complete knapsack be traversed in sequence? Briefly explain

2022-07-07 00:00:00 Fairy Tales

Complete backpack means that each item can be put into the backpack many times .

dp[j] = max(dp[j], dp[j - weight[i]] + value[i])
dp[6] = max(dp[6], dp[6 - 1] + 2)
      = max(dp[6], max(dp[5], dp[5 - 1] + 2) + 2)

dp[j] The capacity is j The maximum value of your backpack with items .
1 It means the first one i The weight of each item ,2 It means the first one i The value of an article .
Initial dp[5] and dp[6] All for 0.
here , Because initially dp[6] yes 0, So I must have chosen dp[6 - 1] + 2, That is to say, it must have been put into No i Items .
and dp[6]=…… The implementation of requires dp[5] Result .
Because it is executed sequentially , therefore dp[6] It must have been implemented before implementation dp[5]=…….
dp[5]=…… Execution time , Because initially dp[5] yes 0, So I must have chosen dp[5 - 1] + 2, That is to say, it must also be put into No i Items .
So the first i Items have been put in many times .
So the complete knapsack should be traversed in sequence .

原网站

版权声明
本文为[Fairy Tales]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/187/202207061616230910.html