题目:宝物筛选    考察内容:多重背包优化      题目链接:P1776 宝物筛选 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路:二进制拆分是一种简单而有效的技巧。原理简单,这道题就是将每种物品的数量进行二进制的拆分,例如若第i种物品的数量有25个,所以可以拆成25=16+8+1,这些2的倍数显然只有log2_X个,所以将原先的复杂度优化到了log级别。
注意拆分的具体实现:不能全部拆成2的倍数,而是先按2的倍数从小到大拆,最后是一个小于或等于最大倍数的余数,如此拆分的目的是为了保证拆出来的树相加不会大于mi
#include <bits/stdc++.h>
#define ios                               \
    ios::sync_with_stdio(false); \
    cin.tie(nullptr);                     \
    cout.tie(nullptr)
#define rep(i,a,n) for(int i=a;i<=n;i++)
#define per(i,a,n) for(int i=n;i>=a;i--)
#define lowbit(x)  ((x) & - (x))
#define pb push_back
#define SZ(v) ((int)v.size())
#define PI acos(-1)
#define x first
#define y second
#define mem(a,b) memset((a),(b),sizeof(a))
using namespace std;
typedef long long ll;
const int INF=0x3f3f3f3f; 
const ll LLINF=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-6;
const int MAX=2e5+10;
const ll mod=1e9+7;
/********************************* std-head *********************************/
const int N=1e5+10;
int n,C,dp[N];
int w[N],c[N],m[N];
int new_n;           //二进制拆分后的新物品的总数量 
int new_w[N],new_c[N],new_m[N];  //二进制拆分后的新物品
int main(){
	ios;
	cin>>n>>C;
	rep(i,1,n) cin>>w[i]>>c[i]>>m[i];
//以下为二进制拆分的思想
    int new_n=0;
	rep(i,1,n){
		for(int j=1;j<=m[i];j<<=1)  //二进制枚举:1,2,4... 
		{
			m[i]-=j;       //减去已拆分的,算剩下需要拆分的值 
			new_c[++new_n]=j*c[i];
			new_w[new_n] = j*w[i];
			
		}
		if(m[i]){   // 最后一个数是余数 
			new_c[++new_n]=m[i]*c[i];
			new_w[new_n]=m[i]*w[i];
		}
	}	
//一下是滚动数组版本的0/1背包
	rep(i,1,new_n)   //枚举物品 
	per(j,new_c[i],C) //枚举背包容量 
	dp[j]=max(dp[j],dp[j-new_c[i]]+new_w[i]);
	cout<<dp[C]<<endl; 
	
	
	return 0;
}