文章目錄

• 題目描述
• 解析
• • 樸素算法
  • • 代碼
  • 二進(jìn)制優(yōu)化
  • • 代碼
• thanks for reading!

題目描述

解析

樸素算法

首先考慮樸素算法
把數(shù)量為num的物體拆成num個(gè)子物體
其價(jià)值與重量是原物體的1，2，3…num倍
然后當(dāng)成獨(dú)立的物體求就行了
注意應(yīng)該先枚舉重量，再枚舉子物體
因?yàn)檫@些子物體是不能同時(shí)取的 (因?yàn)橥瑫r(shí)取時(shí)，總個(gè)數(shù)可能會(huì)超過(guò)num）
時(shí)間復(fù)雜度：nwm
（這題這做法也能過(guò)就離譜）

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int N=1e6+100; int m,n; int W,f[N]; struct node{int v,w,num; }p[N]; int main(){scanf("%d%d",&n,&W);for(int i=1;i<=n;i++){scanf("%d%d%d",&p[i].v,&p[i].w,&p[i].num);}for(int i=1;i<=n;i++){for(int ww=W;ww>=p[i].w;ww--){for(int k=1;k<=p[i].num;k++){if(p[i].w*k>ww) break;f[ww]=max(f[ww],f[ww-p[i].w*k]+k*p[i].v);}}}int ans=0;for(int i=0;i<=W;i++){ans=max(ans,f[i]);}printf("%d",ans);return 0; } /* 4 20 3 9 3 5 9 1 9 4 2 8 1 3 */

二進(jìn)制優(yōu)化

剛才的枚舉拆分顯然十分低效
我們?nèi)绾尾拍馨盐锲凡鸱值男侍岣吣?#xff1f;
我們嘗試把每樣物品拆成完全獨(dú)立的物品
（也就是說(shuō)可以同時(shí)取）
那么我們的拆分應(yīng)不重不漏，也就是要滿足以下條件：

1.加在一起不能超過(guò)總數(shù)量
2.能組合表示出1-num的所有數(shù)

顯然要考慮二進(jìn)制
定義sum數(shù)組：

sum[k]= 2⁰ + 2¹ +2²+… + 2^k

找到一個(gè)最大的k，滿足：

sum[k]<=num

再讓：

R=num-sum[k]

這樣我們把物品拆成k+2個(gè)
其大小分別為：

2⁰、 2¹、2²、… 2^k、R

由于R是減出來(lái)的，加起來(lái)肯定不會(huì)超過(guò)num，條件1成立了

第二個(gè)條件，能表示出1-num的所有數(shù)的證明，可以分成兩部分：
1.對(duì)于<=sum[k]的數(shù)，顯然可以用2的0-k次冪用二進(jìn)制拆分表示出來(lái)

2.對(duì)與>2^k的數(shù)A，把它減去R，也就是先拆出來(lái)一個(gè)R，由R的定義可得：

A-R <= num-R = sum[k]

這樣減去后又是一個(gè)<=sum[k]的數(shù)，就轉(zhuǎn)化為情況1了
條件二證畢
（具體的代碼實(shí)現(xiàn)中，我預(yù)處理了一個(gè)數(shù)組q[i]存儲(chǔ)num為i時(shí)符合條件的k值）
時(shí)間復(fù)雜度：nwlog（m）

代碼

#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #include<iostream> #define ll long long #define mem(a,b) memset(a,b,sizeof(a)) using namespace std; const int N=1e6+100; int m,n; ll W,f[N]; struct node{int v,w,num; }p[N]; int mi[50],q[N],sum[50]; void solve(){mi[0]=1;for(int i=1;i<=30;i++) mi[i]=mi[i-1]*2;sum[0]=1;q[1]=q[2]=0;int res=1,now=3;for(int k=1;k<=18;k++){res+=mi[k];for(int i=now;i<res;i++) q[i]=k-1;now=res;sum[k]=res;} } int main(){scanf("%d%d",&n,&W);for(int i=1;i<=n;i++){scanf("%d%d%d",&p[i].v,&p[i].w,&p[i].num);}solve();for(int i=1;i<=n;i++){int k=q[p[i].num];for(int j=0;j<=k;j++){ll nw=p[i].w*mi[j],nv=p[i].v*mi[j];for(int p=W;p>=nw;p--){f[p]=max(f[p],f[p-nw]+nv);}}int r=p[i].num-sum[k];ll nv=p[i].v*r,nw=p[i].w*r;for(int p=W;p>=nw;p--){f[p]=max(f[p],f[p-nw]+nv);}}ll ans=0;for(int i=0;i<=W;i++){ans=max(ans,f[i]);}printf("%lld",ans);return 0; } /* 4 20 3 9 3 5 9 1 9 4 2 8 1 3 */

thanks for reading!

總結(jié)

以上是生活随笔為你收集整理的多重背包的二进制优化（ybtoj-宝物筛选）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。