Luogu P1776: Treasure Screening ← Multiple Knapsack Problem Binary Optimization

[Title Source]
https://www.luogu.com.cn/problem/P1776

【Title Description】
Finally, the thousand-year-old problem has been solved.Xiao F found the treasure room of the royal family, which was filled with countless valuable treasures.
Now Xiao F can make a fortune, quack.But there are too many treasures here, and Xiao F's collection car seems to be unable to hold so many treasures.It seems that Xiao F can only abandon some of the treasures with tears.
Xiao F sorted out the treasures in the cave and found that each treasure has one or more pieces.He roughly estimated the value of each treasure, and then started the treasure screening work: Xiao F has a collection vehicle with a maximum load of W, and there are a total of n kinds of treasures in the cave. The value of each treasure is vi and the weight is wi,There are mi pieces of each treasure.Xiao F hopes to select some treasures to be loaded into the collection vehicle to maximize their value on the premise that the collection vehicle is not overloaded.

[Input format]
The first line is an integer n and W, which represent the number of treasure species and the maximum load of the collection vehicle, respectively.
The next n lines each contain three integers vi, wi, mi.

[Output Format]
The output is only an integer, which represents the maximum value of the treasure collected under the condition that the collection truck is not overloaded.

[Algorithm Analysis]
Multiple knapsack problems can usually be transformed into 01 knapsack problems to solve.However, if the quantity of each item is split into multiple 1s, the time complexity will be very high, resulting in TLE.Therefore, it is necessary to use binary optimizationidea.That is:
A positive integer n can be decomposed into1,2,4,…,2^(k-1),n-2^k+1.where k is the largest integer that satisfies n-2^k+1>0.

For example, assuming an item with a value of 2 and a quantity of 10, 10 can be decomposed into 1+2+4+3 according to the idea of ​​binary optimization, then the original valueItems with a value of 2 and a quantity of 10 can be equivalently converted into items with a value of 1*2, 2*2, 4*2, 3*2, that is, items with a value of 2, 4, 8, 6, and a quantity of 1..

[Algorithm Code]

#include using namespace std;int n,V;const int maxn=100005;int vol[maxn],val[maxn];int c[maxn];int main() {cin>>n>>V;int cnt=0;for(int i=1; i<=n; i++) {int wi,vi,type;cin>>vi>>wi>>type;int k=1;while(k<=type) {cnt++;vol[cnt]=wi*k;val[cnt]=vi*k;type-=k;k*=2;}if(type>0) {cnt++;vol[cnt]=wi*type;val[cnt]=vi*type;}}n=cnt;for(int i=1; i<=n; i++) {for(int j=V; j>=vol[i]; j--)c[j]=max(c[j],c[j-vol[i]]+val[i]);}cout<



[References]
https://blog.csdn.net/hnjzsyjyj/article/details/109363826
https://www.luogu.com.cn/problem/P1776