$$逃亡的準(zhǔn)備$$

ssl 1236
類似一樣題目（除數(shù)組范圍外）:ssl 2289（慶功會(huì)）

題目大意：

有n個(gè)物品，每個(gè)物品可以選l[i]個(gè),每個(gè)的代價(jià)為a[i],價(jià)值為b[i]，在代價(jià)不大于m的情況下，價(jià)值最大是多少

---

Description

在《Harry Potter and the Deathly Hallows》中，Harry Potter他們一起逃亡，現(xiàn)在有許多的東西要放到赫敏的包里面，但是包的大小有限，所以我們只能夠在里面放入非常重要的物品，現(xiàn)在給出該種物品的數(shù)量、體積、價(jià)值的數(shù)值，希望你能夠算出怎樣能使背包的價(jià)值最大的組合方式，并且輸出這個(gè)數(shù)值，赫敏會(huì)非常地感謝你。

Input

（1）第一行有2個(gè)整數(shù)，物品種數(shù)n和背包裝載體積v。

（2）2行到n+1行每行3個(gè)整數(shù)，為第i種物品的數(shù)量m、體積w、價(jià)值s。

Output

僅包含一個(gè)整數(shù)，即為能拿到的最大的物品價(jià)值總和。

Sample Input

2 10

3 4 3

2 2 5

Sample Output

13

Hint

【注釋】

選第一種一個(gè)，第二種兩個(gè)。

結(jié)果為3×1+5×2=13

【數(shù)據(jù)規(guī)模】

對(duì)于30%的數(shù)據(jù)

1<=v<=500

1<=n<=2000

1<=m<=10

1<=w<=20

1<=s<=100

對(duì)于100%的數(shù)據(jù)

1<=v<=500

1<=n<=2000

1<=m<=5000

1<=w<=20

1<=s<=100

---

$TLE$方法

注釋：

小數(shù)據(jù)可以用

在01背包的基礎(chǔ)上加上一重循環(huán)，來枚舉種數(shù)，就可以TLE了

#include<cstdio> #include<iostream> using namespace std; int n,m,l,v,s,f[505]; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d%d%d",&l,&v,&s);for (int j=m;j>=v;j--)for (int k=0;k<=l;k++)//加個(gè)k用于枚舉種數(shù)if (j>=v*k)//判斷出界未f[j]=max(f[j],f[j-v*k]+s*k);//代價(jià)和}printf("%d",f[m]); }

---

$AC$方法

將每一種物品的數(shù)量分為不同的組，每一組是上一組的兩倍，比如有3個(gè)時(shí)，分為1個(gè)和2個(gè)，這樣1就直接用1,2就直接用2,3就用1加2

當(dāng)有四個(gè)時(shí)就是1,2,1，因?yàn)槭紫纫ＷC總和與l一樣，其次4就是1+2+1,1怎么來的呢：1×2×2=4，但4-1-就只剩下1了,1<4，所以就直接用1，否則兩倍兩倍地乘

#include<cstdio> #include<iostream> #include<cstring> using namespace std; int n,m,w,l,x,y,t,s[50005],v[50005],f[505]; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++){scanf("%d%d%d",&l,&x,&y);t=1;//原本為1while (l>t)//判斷是否可以存{v[++w]=x*t;//w為總個(gè)數(shù)，代價(jià)要加倍s[w]=y*t;//價(jià)值也要加倍l-=t;//l為剩下的t*=2;//t翻倍}if (l)//判斷是否有{v[++w]=x*l;//存s[w]=y*l;//再存}}for (int i=1;i<=w;i++)for (int j=m;j>=v[i];j--)f[j]=max(f[j],f[j-v[i]]+s[i]);//當(dāng)做01背包來做printf("%d",f[m]); }

總結(jié)

以上是生活随笔為你收集整理的【背包】逃亡的准备 （ssl 1236）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

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