Complete backpack beginner chapter "suggestions collection"

Hello everyone , I meet you again , I'm your friend, Quan Jun .

More information about backpacks can be found in my “ knapsack ” View in category

One 、 subject

Yes ｎ Class items and a capacity of ｍ The backpack , Each item has an unlimited number of items available . Put in the i The cost of each item is ｖ i , The value is W i . solve : What items to pack in the backpack , The total cost of these items can not exceed that of the backpack Capacity , And the sum of values is the largest .

Two 、 The basic idea

Complete backpack and ０１ The difference between backpacks is ,０１ There is only one item in the backpack , The complete backpack has an infinite number of items . Let's think in terms of two-dimensional arrays , We are ０１ Every time the value is updated in the knapsack, the decision is whether to put it in the first place ｉ Item , And in the complete backpack , What we need to choose is , We are going to put No ｉ Several items ？（０—— The maximum number of pieces can be put ）

State transition equation :F[i,j]=max{F[i-1,j],F[i-1,j-k*wi]+k*vi}

The total complexity can be thought of as O(mn ∑ni=0m/vi \sum_{i=0}^n m/vi ) This complexity is very large , We need to improve this complexity .

3、 ... and 、 Simple optimization

If two items i , j Satisfy v i ≤ v j And w i ≥ w j , Then you will be able to j Directly remove , Don't have to consider . This optimization method does not satisfy the worst case , Maybe some topics can use this optimization card to pass the time , Therefore, there is not much description here .

Four 、 Better optimization

Considering the i You can choose the most items m/v i Pieces of , So you can put i Items are converted into m /v i An article of constant cost and value , And then solve this 01 knapsack problem . This does not optimize too much complexity . At this time, we can optimize again through the binary idea , Tied together by several identical items , Add it up and we get each value （ such as , Now our first item （ Just call him ａ） The best we can do is ５ Pieces of , So let's take a few ａ Tie it up , The first one ａ, The second two ａ, The third four ａ. We can find that the combination of these parts can be completed １－５ Pieces of ａ Into the backpack of the case of traversal ） In this way, each item is divided into O(log ⌊V /C i ⌋) Item , It's a big improvement . Of course, this is still not the best optimization , We still don't use .

5、 ... and 、O(V N ) The algorithm of

Or to ０１ Start with the direction of the backpack ,０１ Knapsack our final optimization method is to use a one-dimensional array , We traverse from the back to the front , Why? ？ We compare the status of the item that has not been loaded yet , So , From the back to the front, data changes can be prevented , At this time, we need to change the data , What we need is that we have selected No ｉ Sub results of items ,（ For example, we compare whether to put two first items , What are we comparing ？ It is the value of putting one first item and the value of putting two first items ） So at this time, we just need to traverse the second loop from front to back .

CODE:

#include<cstdio>
#include<algorithm>
using namespace std;
int w[300],c[300],f[300010];
int V,n;
int main()
{
    scanf("%d%d",&V,&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d%d",&w[i],&c[i]);
    }
    for(int i=1; i<=n; i++)
        for(int j=w[i]; j<=V; j++)// Notice here , And 0-1 Different backpacks , Here is the order ,0-1 Backpacks are in reverse order 
            f[j]=max(f[j],f[j-w[i]]+c[i]);
    printf("max=%d\n",f[V]);
    return 0;
}

Copy

Publisher ： Full stack programmer stack length , Reprint please indicate the source ：https://javaforall.cn/150680.html Link to the original text ：https://javaforall.cn