Multi knapsack explanation of dynamic programming knapsack problem

Previous articles on knapsack ：

1. 01 Backpack details
2. Complete knapsack explanation
   

One 、 What is the multiple knapsack problem ？

Yes n Items , The volume of each item is v[i], Value is w[i]. The existing one has a capacity of V The backpack , Ask how to select items to put into the backpack , Make the total value of the items in the backpack the largest . Each of these items has s[i] Pieces of .
Multiple backpacks and full backpacks 、01 Backpacks are different ：

1. 01 There are only two situations when choosing an item in the backpack: not choosing it and choosing it once
2. Complete backpack can choose a certain item without , You can also choose once , Choose twice ... There is no upper limit to the number of choices （ As long as the backpack can be put down ）
3. Multiple backpacks can choose an item without , You can choose once 、 secondary ... You can only choose s[i] Time （ As long as the backpack can be put down ）

Two 、 Example analysis

1. subject ：

It is not easy to see the rule in the sample of the original test , So use other test samples ：
sample input ：
3 7qu
2 3 12
2 5 15
1 2 3
sample output ：
12

2. The first one is ： Simple approach

01 knapsack ： The first i This item can be taken from 0 Pieces of , Can take 1 Pieces of
Multiple backpack ： The first i This item can be taken from 0 Pieces of , take 1 Pieces of 、 take 2 Pieces of ······ take s[i] Pieces of
Multiple backpacks are transformed into 01 Knapsack solving ： The first i Items replaced s[i] Pieces of 01 Items in the backpack , The volume of each article is k* v[i], Value is k * w [i] (0<=k<=s[i])
Core code ：

for(i=1;i<=n;i++)
	for(j=m;j>=v[i];j--)
		for(k=0;k<=s[i]&&k*v[i]<=j;k++)
			f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);

3. The second kind ： Binary optimization

The example can be expressed as ：

Binary optimization core code ：

    int cnt=0;// Counter 
    for(int i=1;i<=n;i++)
    {
    
        int a,b,s;
        cin>>a>>b>>s;
        int k=1;
        // Binary split 
        while(k<=s)
        {
    
            cnt++;
            v[cnt]=a*k;
            w[cnt]=b*k;
            s-=k;
            k*=2;
        }
        if(s>0)// The remaining 
        {
    
            cnt++;
            v[cnt]=a*s;
            w[cnt]=b*s;
        }
    }

After splitting, it becomes ：

Use it once after optimization 01 knapsack ：

    for(int i=1;i<=cnt;i++)
        for(int j=m;j>=v[i];j--)
            f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;

4. The second kind ： Monotonic queue optimization < To be written >