? ? ? ? 慶功會（ssl 2289）

Description

為了慶賀班級在校運動會上取得第一名的成績，班主任決定開一場慶功會，為此拔款購買獎品獎勵運動員，期望拔款金額能購買最大價值的獎品，可以補充他們的精力和體力。

Input

第一行二個數n(n<=500)，m(m<=5000)，其中n代表希望購買的物品的種數，m表示班會撥的錢數。
接下來n行，每行3個數，v、w、s，分別表示第I種物品的價格、價值（價格 與 價值 是不同的概念）和購買的數量（只能買0件或s件），其中v<=100,w<=1000,s<=10

Output

第一行：一個數，表示此次購買能獲得的最大的價值（注意！不是價格）。

Sample Input

?

5 1000 80 20 4 40 50 9 30 50 7 20 20 1

?

Sample Output

?

1040

解題方法

01背包改一改就可以了。

代碼

#include<iostream> using namespace std; int a[501],b[501],f[6001],m,n,j,s[501]; int main() { cin>>n>>m; for (int i=1;i<=n;i++) { cin>>a[i]>>b[i]>>s[i];} for (int i=1;i<=n;i++) for (int c=m;c>=a[i];c--) for(int k=0;k<=s[i];k++)//循環種數 { if (c-a[i]*k<0) break; //判斷有沒有越界 f[c]=max(f[c],f[c-a[i]*k]+b[i]*k); //c不變，代價和價值乘種數 } cout<<f[m]; }

?

二進制優化

?

? #include<iostream> using namespace std; int f[6001],a[1001],b[1001],n,m,u; int main() { cin>>n>>m; for (int i=1;i<=n;i++) { int x,y,s,t=1; cin>>x>>y>>s; while (s>t) { a[++u]=x*t;//分成不同數量的物品，并保證可以合成最大數以下的任意一個數 b[u]=y*t; s=s-t; t=t*2; } a[++u]=x*s;//余數 b[u]=y*s; } for (int i=1;i<=u;i++) for (int j=m;j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]+b[i]);//01背包 cout<<f[m]; }

?

?

?

? ? ? 混合背包（ssl 2301）

?

Description

背包體積為V ,給出N個物品，每個物品占用體積為Vi,價值為Wi,每個物品要么至多取1件，要么至多取mi件（mi > 1） , 要么數量無限 ， 在所裝物品總體積不超過V的前提下所裝物品的價值的和的最大值是多少？

Input

第一行兩個數V,N下面N行每行三個數Vi,Wi,Mi表示每個物品的體積，價值與數量，Mi=1表示至多取一件，Mi>1表示至多取Mi件，Mi=0表示數量無限

Output

1個數Ans表示所裝物品價值的最大值

Sample Input

?

10 3 2 1 0 3 3 1 4 5 4

?

Sample Output

?

11

?

解題方法

在循環里加一個判斷，是0用完全背包，不是0用多重背包。

代碼

?

#include<iostream> using namespace std; int a[501],b[501],f[6001],m,n,j,s[501]; int main() { cin>>m>>n; for (int i=1;i<=n;i++){cin>>a[i]>>b[i]>>s[i];} for (int i=1;i<=n;i++)if (s[i]==0)//判斷是多重背包還是完全背包for (int c=a[i];c<=m;c++)//完全背包f[c]=max(f[c],f[c-a[i]]+b[i]); else for (int c=m;c>=a[i];c--)//多重背包for(int k=0;k<=s[i];k++){if (c-a[i]*k<0) break;//判斷有沒有越界 f[c]=max(f[c],f[c-a[i]*k]+b[i]*k); } cout<<f[m]; }

?

?

?

?

?

?

? ? ? 分組背包（ssl 2291）

?

Description

有N件物品和一個容量為V的背包。第i件物品的費用是c[i]，價值是w[i]。這些物品被劃分為若干組，每組中的物品互相沖突，最多選一件。求解將哪些物品裝入背包可使這些物品的費用總和不超過背包容量，且價值總和最大。

Input

第一行：三個整數，v(背包容量，v<=200),n（物品數量，n<=30)和t（最大組號，t<=10）;
第2..n+1行：每行三個整數wi,ci,p，表示每個物品的重量、價值、所屬組號。

Output

僅一行，一個數，表示最大總價值。

Sample Input

?

10 6 3 2 1 1 3 3 1 4 8 2 6 9 2 2 8 3 3 9 3

?

Sample Output

?

20

解題方法

把同組的放在一個數組里，再加多一個循環就可以了。

代碼

?

#include<iostream> using namespace std; int v,y,u,a[300][300],b[300][300],f[1000],p[11],m,n,t; int main() { for (int i=1;i<=10;i++)p[i]=0; cin>>m>>n>>t; for (int i=1;i<=n;i++){cin>>v>>y>>u;a[u][++p[u]]=v;//p[u]用于放第u組有多少個物品b[u][p[u]]=y;//第u組第p[u]個的價格和價值} for (int i=1;i<=t;i++)//第幾組for (int j=m;j>=0;j--)for (int c=1;c<=p[u];c++)//第幾個if (j>=a[i][c])//判斷有沒有越界f[j]=max(f[j],f[j-a[i][c]]+b[i][c]); cout<<f[m]; }

?

?

?

?

?

? ? ? ? ? 貨幣系統（ssl 1115）

?

Description

母牛們不但創建了他們自己的政府而且選擇了建立了自己的貨幣系統。
[In their own rebellious way]，他們對貨幣的數值感到好奇。
傳統地，一個貨幣系統是由1,5,10,20 或 25,50, 和 100的單位面值組成的。
母牛想知道有多少種不同的方法來用貨幣系統中的貨幣來構造一個確定的數值。
舉例來說, 使用一個貨幣系統 {1,2,5,10,...}產生 18單位面值的一些可能的方法是:18x1, 9x2, 8x2+2x1, 3x5+2+1,等等其它。
寫一個程序來計算有多少種方法用給定的貨幣系統來構造一定數量的面值。
保證總數將會適合long long (C/C++) 和 Int64 (Free Pascal)。

Input

貨幣系統中貨幣的種類數目是 V 。 (1<= V<=25)
要構造的數量錢是 N 。 (1<= N<=10,000)
第 1 行: 二整數， V 和 N
第 2 ..V+1行： 可用的貨幣 V 個整數　(每行一個　每行沒有其它的數)。

Output

單獨的一行包含那個可能的構造的方案數。
末尾有空行

Sample Input

?

3 10 1 2 5

?

Sample Output

?

10

解題方法

累加之前的組數就可以了。

代碼

? #include<iostream> using namespace std; int m,n,a[30]; long long f[10100]; int main() { cin>>m>>n; for (int i=1;i<=m;i++) cin>>a[i]; f[0]=1;//預處理 for (int i=1;i<=m;i++) for (int j=a[i];j<=n;j++) f[j]=f[j]+f[j-a[i]];//用a[i]的錢時等于其他錢組成的種數加上用a[i]之前的種數 cout<<f[n]; }

?

?

?

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的背包系列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。