【题目描述】
辰辰是个很有潜能、天资聪颖的孩子，他的梦想是称为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”
如果你是辰辰，你能完成这个任务吗？
【输入】
输入的第一行有两个整数T（1≤T≤1000）和M（1≤M≤100），T代表总共能够用来采药的时间，M代表山洞里的草药的数目。接下来的M行每行包括两个在1到100之间（包括1和100）的的整数，分别表示采摘某株草药的时间和这株草药的价值。
【输出】
输出只包括一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。
【输入样例】
70 3 71 100 69 1 1 2
【输出样例】
3
又是一道背包水题，估计应该是红题里的佼佼者，但还是没黄题好玩...啧啧啧
其实我写这篇博客只是单纯为了列代码方便以后抄
巨佬们都看出来是背包了对吧
做完我才发现
多么阔爱的一个01背包，代码都不带改的（大雾
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<string> 5 #include<cmath> 6 #include<algorithm> 7 #include<cstdlib> 8 using namespace std; 9 const int maxm=1001,maxn=101; 10 int m,n; 11 int w[maxn],c[maxn]; 12 int f[maxn][maxm]; 13 int max(int x,int y) 14 { 15 if(x>y) 16 return x; 17 else return y; 18 } 19 int main() 20 { 21 scanf("%d%d",&m,&n); 22 for(int i=1;i<=n;i++) 23 scanf("%d%d",&w[i],&c[i]); 24 for(int i=1;i<=n;i++) 25 for(int v=m;v>0;v--) 26 if(w[i]<=v) 27 f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]); 28 else f[i][v]=f[i-1][v]; 29 printf("%d",f[n][m]); 30 return 0; 31 }
这是采药的代码，那我们再来看看01背包的
就尼玛离谱
#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<cmath> #include<algorithm> #include<cstdlib> using namespace std; const int maxm=201,maxn=31; int m,n; int w[maxn],c[maxn]; int f[maxn][maxm]; int max(int x,int y) { if(x>y) return x; else return y; } int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int v=m;v>0;v--) if(w[i]<=v) f[i][v]=max(f[i-1][v],f[i-1][v-w[i]]+c[i]); else f[i][v]=f[i-1][v]; printf("%d",f[n][m]); return 0; }
来都来了对吧
那让我们看看其他背包的标准代码
改几个语句就能用的那种
//完全背包 //设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为M，今从n种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于M，而价值的和为最大。 //看亿段伪代码 const int maxm=201,maxn=31; int m,n; int w[maxn],c[maxn]; int f[maxn][maxm]; int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d",&w[i],&c[i]); for(int i=1;i<=n;i++) for(int v=1;v<=m;v++) if(v<w[i]) f[i][v]=f[i-1][v]; else if(f[i-1][v]>f[i][v-w[i]]+c[i]) f[i][v]=f[i-1][v]; else f[i][v]=f[i][v-w[i]]+c[i]; printf("max=%d",f[n][m]); return 0; }
//混合背包 //一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。有的物品只可以取一次（01背包），有的物品可以取无限次（完全背包），有的物品可以取的次数有一个上限（多重背包）。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 int m,n; int w[31],c[31],p[31]; int f[201]; int max(int x,int y) { if(x>y) return x; else return y; } int main() { scanf("%d%d",&m,&n); for(int i=1;i<=n;i++) scanf("%d%d%d",&w[i],&c[i],&p[i]); for(int i=1;i<=n;i++) if(p[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<=p[i];j++) for(int k=m;k>=w[i];k--) f[k]=max(f[k],f[k-w[i]]+c[i]); } cout<<f[m]; return 0;
//分组背包 //一个旅行者有一个最多能装V公斤的背包，现在有n件物品，它们的重量分别是W1，W2，...,Wn，它们的价值分别为C1,C2,...,Cn。这些物品被划分为若干组，每组中的物品互相冲突，最多选一件。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量，且价值总和最大。 //这旅行者Tm怎么还没被累死（雾 int v,n,t; int w[31],c[31]; int a[11][32],f[201]; int main() { scanf("%d%d%d",&v,&n,&t); for(int i=1;i<=n;i++) { int p; scanf("%d%d%d",&w[i],&c[i],&p); a[p][++a[p][0]]=i; } for(int k=1;k<=t;k++) for(int j=v;j>=0;j--) for(int i=1;i<=a[k][0];i++) if(j>=w[a[k][i]]) { int tmp=a[k][i]; if(f[j]<f[j-w[tmp]]+c[tmp]) f[j]=f[j-w[tmp]]+c[tmp]; } printf("%d",f[v]); return 0; }