The famous NP-complete problem. The problem of putting the item in the knapsack so that the value of the item is maximized.
If you think simply, it will be $ O (2 ^ N) $ because you will have to choose not to put the item in. Consider solving this in polynomial time.
We will explain how to solve these in polynomial time in three steps.
As an image of dynamic programming, consider increasing from a small state. In other words, think from one time. At one time, it is decided whether to put it in or not depending on the capacity of the knapsack. Of course, it is more valuable to put it in, so put it in. At the second time, decide whether to put it in the knapsack. What you should be careful about here is the branch with the first one in it. The decision whether to put it in the knapsack is divided. And at the third time, compare it with the knapsack at the end of the second one. In other words, it is the miso of this problem to think about whether to add a new item to the existing state.
In production
Recommended Posts