题目:宝物筛选 考察内容:多重背包优化 题目链接: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; }