?

53. 多人背包

★☆?? 輸入文件：bags.in?? 輸出文件：bags.out?? 簡單對比
時(shí)間限制：2 s?? 內(nèi)存限制：128 MB

?

問題描述 DD 和好朋友們要去爬山啦！他們一共有 K 個(gè)人，每個(gè)人都會(huì)背一個(gè)包。這些包的容量是相同的，都是 V。可以裝進(jìn)背包里的一共有 N 種物品，每種物品都有給定的體積和價(jià)值。 在 DD 看來，合理的背包安排方案是這樣的：

每個(gè)人背包里裝的物品的總體積恰等于包的容量。

每個(gè)包里的每種物品最多只有一件，但兩個(gè)不同的包中可以存在相同的物品。

任意兩個(gè)人，他們包里的物品清單不能完全相同。

在滿足以上要求的前提下，所有包里的所有物品的總價(jià)值最大是多少呢？ 輸入格式 第一行有三個(gè)整數(shù)：K、V、N。 第二行開始的 N 行，每行有兩個(gè)整數(shù)，分別代表這件物品的體積和價(jià)值。 輸出格式 只需輸出一個(gè)整數(shù)，即在滿足以上要求的前提下所有物品的總價(jià)值的最大值。 樣例輸入 2 10 5 3 12 7 20 2 4 5 6 1 1 樣例輸出 57 樣例說明 一種可以得到最優(yōu)解的方案是：第一個(gè)人背體積為 7、2、1 的三種物品，價(jià)值為 25。第二個(gè)人背體積為 3、7 的兩種物品，價(jià)值為 32。總價(jià)值 57。 數(shù)據(jù)范圍 總?cè)藬?shù) K<=50。 每個(gè)背包的容量 V<=5000。 物品種類數(shù) N<=200。 其它正整數(shù)都不超過 5000。 輸入數(shù)據(jù)保證存在滿足要求的方案。

AC代碼：

?

//背包問題第K優(yōu)解 #include<cstdio> #include<cstring> using namespace std; const int N=5e4+5; int n,m,K,ans,f[55][N],q1[N],q2[N]; int main(){freopen("bags.in","r",stdin); freopen("bags.out","w",stdout); scanf("%d%d%d",&K,&m,&n);memset(f,-0x3f,sizeof f);//*****f[1][0]=0;//f[i][j]表示第i個(gè)人在體積容量為j下可獲得的最大價(jià)值for(int i=1,v,c;i<=n;i++){scanf("%d%d",&v,&c);for(int j=m;j>=v;j--){for(int k=1;k<=K;k++){q1[k]=f[k][j];q2[k]=f[k][j-v]+c;}//f[i][j]=merge(f[k][j-v]+v) 維護(hù)單調(diào)隊(duì)列 //要求每個(gè)最優(yōu) 即累加前k優(yōu)解for(int h1=1,h2=1,cnt=1;cnt<=K;cnt++){if(q1[h1]>q2[h2]) f[cnt][j]=q1[h1++];else f[cnt][j]=q2[h2++];//來自歸并排序 }}}for(int i=1;i<=K;i++) ans+=f[i][m];printf("%d\n",ans);return 0; }

?

轉(zhuǎn)載于:https://www.cnblogs.com/shenben/p/6046198.html

總結(jié)

以上是生活随笔為你收集整理的53. 多人背包的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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