首页 > 代码库 > 01背包专题
01背包专题
>>什么是01背包<<
A - Bone Collector
Time Limit:1000MS Memory Limit:32768KB 64bit IO Format:%I64d & %I64uDescription
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 ?
Input
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.
Output
Sample Input
Sample Output
>>题目链接<<
题意：给定背包容量，骨头的个数和每个骨头的价值，求在背包容量允许的情况下，最多装的价值。
思路：最基础的01背包，dp[j]=max(dp[j],dp[j-w[i]]+v[i])；
#include<cstdio>#include<iostream>using namespace std;int main(){ int N,V,T; int w[1005]; int c[1005]; int i,j,k; scanf("%d",&T); while(T--) { int f[1005]={0}; scanf("%d%d",&N,&V); for(i=0;i<N;i++) { scanf("%d",&w[i]); } for(i=0;i<N;i++) { scanf("%d",&c[i]); } for(i=0;i<N;i++) { // printf("\nc[%d]=%d\tw[%d]=%d\n",i,c[i],i,w[i]); for(int v=V;v>=c[i];v--)// 剩下的体积要大于想放入的体积 { f[v]=max(f[v],f[v-c[i]]+w[i]); // printf("v=%d\tf[%d]=%d\n",v,v,f[v]); } } } return 0;}/*15 102 3 4 5 14 3 2 1 5*/
写的第一个01背包，写的格式不是很好，见谅！
B - Charm Bracelet
Time Limit:1000MS Memory Limit:65536KB 64bit IO Format:%I64d & %I64uDescription
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
>>题目链接<<
题意：输入N，M，表示下面有N组数据（Wi，Di），要求取数据Wi和超过M，同时Di和最大；
分析：典型的01背包，在背包允许的载重范围内，使得价值最大！
#include<cstdio>#include<iostream>using namespace std;int main(){ int N,M; int W[3500],D[3500]; int i,j,k; while(scanf("%d%d",&N,&M)!=EOF) { int f[12885]={0}; for(i=0;i<N;i++) { scanf("%d%d",&W[i],&D[i]); } for(i=0;i<N;i++) { for(j=M;j>=W[i];j--) { // if(f[j]<f[j-W[i]]+D[i]) // f[j]=f[j-W[i]]+D[i]; f[j]=max(f[j],f[j-W[i]]+D[i]);// 注意这里是加上第i的价值哦，不是j； // printf("j=%d\tf[%d]=%d\n",j,j,f[j]); } } printf("%d\n",f[M]); } return 0;}/*4 61 42 63 122 7*/
C -饭卡
Time Limit: 5000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 12642 Accepted Submission(s): 4383
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
题意：首先输入菜的种类n,然后第二行输入n种菜的价格，第三行输入饭卡里的余额；如果饭卡里的钱低于5元，不管够不够，都不能付款，否则可以付款，即使钱不够也没关系，求最多可以买多少的菜，然后饭卡里的余额最少；
思路：把最贵的菜先拿出来，然后再01背包，注意这个时候最大的背包数位m-5;注意m小于5的时候是不能购买的；
>>题目链接<<
#include<cstdio>#include<iostream>using namespace std;int main(){ int n,i,j,m; int c[1005]; int sum,mmax; while(scanf("%d",&n),n) { sum=0; mmax=0; int f[1005]= {0}; for(i=0; i<n; i++) { scanf("%d",&c[i]); sum+=c[i]; mmax=max(mmax,c[i]); } scanf("%d",&m); if(m<5) { printf("%d\n",m); } else if(sum<=m) printf("%d\n",m-sum); else { int t=0; for(i=0; i<n; i++) { if(c[i]==mmax) { c[i]=0; t=1; } if(t) break; } for(i=0; i<n; i++) { for(j=m-5; j>=c[i]; j--) { f[j]=max(f[j],f[j-c[i]]+c[i]); } } printf("%d\n",m-mmax-f[m-5]); } } return 0;}
D - CD
Time Limit:3000MS Memory Limit:0KB 64bit IO Format:%lld & %lluDescription
| CD |
You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.
Assumptions:
- number of tracks on the CD. does not exceed 20
- no track is longer than N minutes
- tracks do not repeat
- length of each track is expressed as an integer number
- N is also integer
Program should find the set of tracks which fills the tape best and print it in the same sequence as the tracks are stored on the CD
Input
Any number of lines. Each one contains value N, (after space) number of tracks and durations of the tracks. For example from first line in sample data: N=5, number of tracks=3, first track lasts for 1 minute, second one 3 minutes, next one 4 minutes
Output
Set of tracks (and durations) which are the correct solutions and string `` sum:" and sum of duration times.
Sample Input
5 3 1 3 410 4 9 8 4 220 4 10 5 7 490 8 10 23 1 2 3 4 5 745 8 4 10 44 43 12 9 8 2
Sample Output
1 4 sum:58 2 sum:1010 5 4 sum:1910 23 1 2 3 4 5 7 sum:554 10 12 9 8 2 sum:45
>>题目链接<<
题意：
这道题给定一个时间上限，然后一个数字N，后面跟着N首歌的时间长度，要我们
求在规定时间w内每首歌都要完整的播放，最多能播放多少时间。一个比较典型的背包问题，
但是要标记出我们选出的歌曲的编号，然后按顺序输出他们的长度，最后输出求的的最长
播放时间。
思路：在经典的背包问题上增加了一个输出路径而已；那么怎么输出路径呢？我们可以从后面往前dp记录vis[i][j]表示i位上体积为j的数，i对应time[i]就是路径；（表达的不好，j=j-time[i]就是上一个最大体积，也就是路径，那么对应的遍历vis是否有标记，有酒读取。。。以此类推。。输出路径。）
#include<cstdio>#include<iostream>using namespace std;int main(){ int N,tracks,i,j; int time[25]; while(scanf("%d%d",&N,&tracks)!=EOF) { int dp[1005]= {0}; int vis[25][1005]={0}; for(i=0; i<tracks; i++) { scanf("%d",&time[i]); } for(i=tracks-1; i>=0; i--) { for(j=N; j>=time[i]; j--) { if(dp[j]<dp[j-time[i]]+time[i]) { dp[j]=dp[j-time[i]]+time[i]; vis[i][j]=1; // printf("vis[%d][%d]\tdp[%d]=%d\n",i,j,j,dp[j]); } } } for(i=0,j=dp[N];i<tracks&&j>0;i++) { if(vis[i][j]) { // printf("vis[%d][%d]=%d\tdp[%d]=%d\t time[%d]=%d\n",i,j,vis[i][j],j,dp[j],i,time[i]); printf("%d ",time[i]); j-=time[i]; } } printf("sum:%d\n",dp[N]); } return 0;}
下面是去掉注释后的运行结果，有助于理解！
当然这道题还可以用状态压缩来做。。。（状态压缩就是把，每个状态表示为01，0表示不包括，1表示包括在内！）不懂的看代码就知道了。。。
#include<cstdio>#include<iostream>using namespace std;int mmax;int main(){ int N,tracks,i,j; int time[25]; while(scanf("%d%d",&N,&tracks)!=EOF) { for(i=0; i<tracks; i++) { scanf("%d",&time[i]); // printf("%d \t",time[i]); } // printf("\n"); mmax=(1<<tracks)-1; // printf("mmax=%d\n",mmax); int p=0,sum,t,temp=0; for(i=mmax; i>0; i--) { t=0; sum=0; // printf("i= %d\n",i); for(j=i; j>0;) { if(j%2) sum+=time[t]; // printf("sum= %d \t",sum); j/=2; t++; } if(sum<=N&&temp<=sum) { temp=sum; p=i; } } t=0; for(j=p; j>0;) { if(j%2) printf("%d ",time[t]); j/=2; t++; } printf("sum:%d\n",temp); } return 0;}
先写到这里了。。。明天继续更新。。。
01背包专题