首页 > 代码库 > 背包专题（持续更新）
背包专题（持续更新）
POJ 3624 Charm Bracelet
题目链接：http://poj.org/problem?id=3624
Description
Bessie has gone to the mall‘s jewelry store and spies a charm bracelet. Of course, she‘d like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a ‘desirability‘ factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 61 42 63 122 7
Sample Output
23
题解：01背包
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <string> 6 using namespace std; 7 int dp[200005]; 8 int main() 9 {10 int n,m;11 while(cin>>n>>m){12 int x,y;13 memset(dp,0,sizeof(dp));14 for(int i=0;i<n;i++){15 cin>>x>>y;16 for(int j=m;j>=x;j--){17 dp[j]=max(dp[j],dp[j-x]+y);18 }19 }20 cout<<dp[m]<<endl;21 }22 return 0;23 }
HDU 2602 Bone Collecter
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2602
The bone collector had a big bag with a volume of V ,and along his trip of collecting there are a lot of bones , obviously , different bone has different value and different volume, now given the each bone’s value along his trip , can you calculate out the maximum of the total value the bone collector can get ?
InputThe first line contain a integer T , the number of cases.
Followed by T cases , each case three lines , the first line contain two integer N , V, (N <= 1000 , V <= 1000 )representing the number of bones and the volume of his bag. And the second line contain N integers representing the value of each bone. The third line contain N integers representing the volume of each bone.OutputOne integer per line representing the maximum of the total value (this number will be less than 2 31).Sample Input
15 101 2 3 4 55 4 3 2 1
Sample Output
14
题解：01背包
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <string> 6 using namespace std; 7 int dp[200005]; 8 int a[1001]; 9 int b[1001];10 int main()11 {12 int n,v,t;13 cin>>t;14 while(t--){15 cin>>n>>v;16 memset(dp,0,sizeof(dp));17 for(int i=0;i<n;i++)18 cin>>a[i];19 for(int i=0;i<n;i++)20 cin>>b[i];21 for(int i=0;i<n;i++){22 for(int j=v;j>=b[i];j--){23 dp[j]=max(dp[j],dp[j-b[i]]+a[i]);24 }25 }26 cout<<dp[v]<<endl;27 }28 return 0;29 }
HDU 2546 饭卡
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2546
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。Sample Input
1505101 2 3 2 1 1 2 3 2 1500
Sample Output
-4532
题解：01背包变形
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <algorithm> 5 using namespace std; 6 int dp[1010]; 7 int val[1010]; 8 int main() 9 {10 int n,i,j,m;11 while(cin>>n&&n){12 memset(dp,0,sizeof(dp));13 memset(val,0,sizeof(val));14 for(int i=0;i<n;i++)15 cin>>val[i];16 cin>>m;17 if(m<5) {18 cout<<m<<endl;19 continue;20 }21 sort(val,val+n);22 int maxn=val[n-1];23 m-=5;24 if(m>=val[0]){25 for(int i=0;i<n-1;++i){26 for(j=m;j>=val[i];--j){27 dp[j]=max(dp[j],dp[j-val[i]]+val[i]);28 }29 }30 }31 cout<<m+5-dp[m]-maxn<<endl;32 }33 return 0;34 }
HDU 2955 Robberies
For a few months now, Roy has been assessing the security of various banks and the amount of cash they hold. He wants to make a calculated risk, and grab as much money as possible.
His mother, Ola, has decided upon a tolerable probability of getting caught. She feels that he is safe enough if the banks he robs together give a probability less than this.
InputThe first line of input gives T, the number of cases. For each scenario, the first line of input gives a floating point number P, the probability Roy needs to be below, and an integer N, the number of banks he has plans for. Then follow N lines, where line j gives an integer Mj and a floating point number Pj .
Bank j contains Mj millions, and the probability of getting caught from robbing it is Pj .OutputFor each test case, output a line with the maximum number of millions he can expect to get while the probability of getting caught is less than the limit set.
Notes and Constraints
0 < T <= 100
0.0 <= P <= 1.0
0 < N <= 100
0 < Mj <= 100
0.0 <= Pj <= 1.0
A bank goes bankrupt if it is robbed, and you may assume that all probabilities are independent as the police have very low funds.Sample Input
30.04 31 0.022 0.033 0.050.06 32 0.032 0.033 0.050.10 31 0.032 0.023 0.05
Sample Output
246
题解：
最重要的是找动态转移方程，可以将所用银行里的钱看作背包容量，每一家银行的钱看作重量，
不被抓到的概率看作价值，则转移方程为：dp[ j ]=max( dp[ j ] , dp[ j - bag[ i ].v]*( 1- bag[ i ].p ) );
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <string> 6 using namespace std; 7 double dp[10010]; 8 struct Bag 9 {10 int v;11 double p;12 }bag[10010];13 int main()14 {15 int n,t;16 double p;17 cin>>t;18 while(t--){19 cin>>p>>n;20 int sum=0;21 for(int i=0;i<n;i++){22 cin>>bag[i].v>>bag[i].p;23 sum+=bag[i].v;24 }25 memset(dp,0,sizeof(dp));26 dp[0]=1;27 for(int i=0;i<n;i++){28 for(int j=sum;j>=bag[i].v;j--){29 dp[j]=max(dp[j],dp[j-bag[i].v]*(1-bag[i].p));30 }31 }32 for(int i=sum;i>=0;i--){33 if(dp[i]>1-p){34 cout<<i<<endl;35 break;36 }37 }38 }39 return 0;40 }
UVA 562 Dividing coins
题目链接：https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=503
题解：最重要的是找动态转移方程，可以将所用银行里的钱看作背包容量，每一家银行的钱看作重量，
不被抓到的概率看作价值，则转移方程为：dp[ j ]=max( dp[ j ] , dp[ j - bag[ i ].v]*( 1- bag[ i ].p ) );
*/
1 #include <iostream> 2 #include <cstdio> 3 #include <algorithm> 4 #include <cstring> 5 #include <string> 6 using namespace std; 7 double dp[10010]; 8 struct Bag 9 {10 int v;11 double p;12 }bag[10010];13 int main()14 {15 int n,t;16 double p;17 cin>>t;18 while(t--){19 cin>>p>>n;20 int sum=0;21 for(int i=0;i<n;i++){22 cin>>bag[i].v>>bag[i].p;23 sum+=bag[i].v;24 }25 memset(dp,0,sizeof(dp));26 dp[0]=1;27 for(int i=0;i<n;i++){28 for(int j=sum;j>=bag[i].v;j--){29 dp[j]=max(dp[j],dp[j-bag[i].v]*(1-bag[i].p));30 }31 }32 for(int i=sum;i>=0;i--){33 if(dp[i]>1-p){34 cout<<i<<endl;35 break;36 }37 }38 }39 return 0;40 }
51 Nod 1085 背包问题
题目链接：https://www.51nod.com/onlineJudge/questionCode.html#!problemId=1085
第1行，2个整数，N和W中间用空格隔开。N为物品的数量，W为背包的容量。(1 <= N <= 100，1 <= W <= 10000)第2 - N + 1行，每行2个整数，Wi和Pi，分别是物品的体积和物品的价值。(1 <= Wi, Pi <= 10000)
输出可以容纳的最大价值。
3 62 53 84 9
14
题解：01背包模板
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 int dp[100005]; 6 int main() 7 { 8 int n,w,x,y; 9 scanf("%d%d",&n,&w);10 memset(dp,0,sizeof(dp));11 for(int i=1;i<=n;i++){12 scanf("%d%d",&x,&y);13 for(int j=w;j>=x;j--){14 dp[j]=max(dp[j],dp[j-x]+y);15 }16 }17 cout<<dp[w]<<endl;18 return 0;19 }
51Nod 1086 背包问题 V2
第1行，2个整数，N和W中间用空格隔开。N为物品的种类，W为背包的容量。(1 <= N <= 100，1 <= W <= 50000)第2 - N + 1行，每行3个整数，Wi，Pi和Ci分别是物品体积、价值和数量。(1 <= Wi, Pi <= 10000， 1 <= Ci <= 200)
输出可以容纳的最大价值。
3 62 2 53 3 81 4 1
9
题解：多重背包
1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 int dp[500005]; 6 int main() 7 { 8 int n,m,w,c,p,k,flag; 9 scanf("%d%d",&n,&m);10 memset(dp,0,sizeof(dp));11 for(int i=1;i<=n;i++){12 scanf("%d%d%d",&w,&p,&c);13 for(k=1,flag=1; ;k*=2){14 if(k*2>=c){15 k=c-k+1;16 flag=0;17 }18 for(int j=m;j >= k*w;j--){19 dp[j]=max(dp[j],dp[j-k*w]+k*p);20 21 }22 if(flag==0) break;23 }24 }25 cout<<dp[m]<<endl;26 return 0;27 }
背包专题（持续更新）