二进制拆分优化 $$O(m\sum logs[i])$$
转换为01背包求解
朴素拆分将c[i],w[i],s[i]
拆分成s[i]
个c[i],w[i]
个01背包,时间复杂度为$$O(m\sum s[i])$$
通过二进制拆分制定一个拆分系数,把元素捆绑在一起,时间复杂度:$$O(m\sum logs[i])$$
$$2^0,2^1,2^2…2^j,s[i]-剩下的$$
ep: s[i]=34
(c[i],w[i])
(2c[i],2w[i])
(4c[i],4w[i])
(8c[i],8w[i])
(16c[i],16w[i])
(3c[i],3w[i])//无法继续拆分
可以发现,通过这种拆分方式,可以等效表示出0-s[i]
的任何一种选择
const int N=2e5+100;
int n,m;int c[N],w[N];int dp[N];
void solve(){
cin>>n>>m;
int idx=0;
while(n--){
int ci,wi,si;cin>>ci>>wi>>si;
for(int j=1;j<=si;j<<=1){//二进制拆分
c[++idx]=j*ci;
w[idx]=j*wi;
si-=j;
}
if(si){//若有剩余
c[++idx]=si*ci;
w[idx]=si*wi;
}
}
f1(i,1,idx)//套01
f3(j,m,c[i])
dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
cout<<dp[m]<<endl;
}