ssl2289-慶功會

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

解題思路

? 枚舉一下選的組數就好了，可以二進制優化。

代碼

#include<cstdio> #include<iostream> using namespace std; int n,m,w[501],c[501],s[501],f[6001]; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) scanf("%d%d%d",&w[i],&c[i],&s[i]);for (int i=1;i<=n;i++)for (int j=m;j>=0;j--)for (int k=0;k<=s[i];k++)//枚舉組數{if (j-k*w[i]<0) break;//判斷越界f[j]=max(f[j],f[j-k*w[i]]+k*c[i]);}printf("%d",f[m]); }

二進制優化代碼

#include<cstdio> #include<iostream> using namespace std; int n,m,w[10001],c[10001],f[6001],n1; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) {int x,y,s,t=1;scanf("%d%d%d",&x,&y,&s);while (s>=t){w[++n1]=x*t;c[n1]=y*t;s-=t;t*=2;}w[++n1]=x*s;c[n1]=y*s;//二進制優化}for (int i=1;i<=n1;i++)for (int j=m;j>=w[i];j--)f[j]=max(f[j],f[j-w[i]]+c[i]);printf("%d",f[m]); }

ssl2301-混合背包

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

解題思路

混合背包，就是多重加完全罷了。

代碼

#include<cstdio> #include<iostream> using namespace std; int n,m,w[31],c[31],f[201],s[31]; int main() {scanf("%d%d",&m,&n);for (int i=1;i<=n;i++) {scanf("%d%d%d",&w[i],&c[i],&s[i]);}for (int i=1;i<=n;i++)if (s[i]==0){for (int j=w[i];j<=m;j++)f[j]=max(f[j],f[j-w[i]]+c[i]);}//完全背包else{for (int j=1;j<=s[i];j++)for (int k=m;k>=w[i];k--)f[k]=max(f[k],f[k-w[i]]+c[i]);}//多重printf("%d",f[m]); }

ssl2291-分組背包

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<cstdio> #include<iostream> using namespace std; int w[31],c[31],a[11][32],f[201],m,n,t,p; int main() {scanf("%d%d%d",&m,&n,&t);for (int i=1;i<=n;i++){scanf("%d%d%d",&w[i],&c[i],&p);a[p][++a[p][0]]=i;//分組}for (int i=1;i<=t;i++)for (int j=m;j>=0;j--)for (int k=1;k<=a[i][0];k++)//枚舉選的組數if (j>=w[a[i][k]])//避免越界{f[j]=max(f[j],f[j-w[a[i][k]]]+c[a[i][k]]);//動態轉移}printf("%d",f[m]); }

ssl1115-貨幣系統

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<cstdio> using namespace std; int a[10001],n,m; long long f[10001]; int main() {scanf("%d%d",&n,&m);for (int i=1;i<=n;i++)scanf("%d",&a[i]);//輸入f[0]=1;//預處理for (int i=1;i<=n;i++)for (int j=a[i];j<=m;j++)f[j]+=f[j-a[i]];//方案數累加printf("%lld",f[m]); }

總結

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

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