Basic knapsack problem

Basic Backpack  

subject

Yes N Items and a capacity for V The backpack . The first i The weight of the item is w[i], The value is v[i]. Solve which items are loaded into the backpack so that the total weight of these items does not exceed the backpack capacity , And the sum of values is the largest .

The basic idea

This is the basic knapsack problem , Characteristic is ： There is only one item of each kind , You can choose to put it or not .

Define states with subproblems ： namely f[i][v] Before presentation i Items are just put into a capacity of v The maximum value that you can get from your backpack . Then State transition equation That is ：

f[i][v]=max{ f[i-1][v], f[i-1][v-w[i]]+v[i] }.

It can compress space ,f[v]=max{f[v],f[v-w[i]]+v[i]}

This equation is very important , Basically, the equations of all knapsack related problems are derived from it . So it is necessary to explain it in detail ：“ Before the i The capacity of items is v In my backpack ” This subproblem , If we only consider i Strategy of items （ With or without ）, Then it can be transformed into a front only i-1 Problems with items . If you don't put the first i Item , Then the problem turns into “ front i-1 The capacity of items is v In my backpack ”, Value is f[i-1][v]; If you put the first i Item , Then the problem turns into “ front i-1 Put items into the remaining capacity of v-w[i] In my backpack ”, The greatest value you can get at this time is f [i-1][v-w[i]] Plus by putting the i The value of items v[i].

Be careful f[v] Meaningful if and only if there is a pre i A subset of items , The total cost is f[v]. So after recursion according to this equation , The final answer is not necessarily f[N] [V], It is f[N][0..V] The maximum of . If the state is defined as “ just ” Remove the word , We have to add another term to the transfer equation f[v-1], So that's a guarantee f[N] [V] That's the final answer . As for why this can , It's up to you to experience .