背包问题全解

#include<cstdio>
using namespace std;
const int maxm=201,maxn=31;
int m,n;
int w[maxn],c[maxn];//weight and cost
int f[maxn][maxm];//f[数量][质量]
int max(int x,int y){
	if(x<y)return y;
	else return x;
}
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;/*10 4
	2 1
	3 3
	4 5
	7 9*/
}

#include<cstdio>
using namespace std;
const int maxm=2001,maxn=31;
int m,n;
int w[maxn],c[maxn];//weight & cost
int f[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=m;v>=w[i];v--)//只要放得下即可，并且不断压缩至正好
			if(f[v-w[i]]+c[i]>f[v])f[v]=f[v-w[i]]+c[i];
	printf("%d",f[m]);
	return 0;
	/*10 4
	2 1
	3 3
	4 5
	7 9*/
}

#include<cstdio>
using namespace std;
const int maxm=201,maxn=31;
int m,n;
int w[maxn],c[maxn];
int f[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=w[i];v<=m;v++)//可以逐渐填入一个w[i],两个w[i]······
           if(f[v-w[i]]+c[i]>f[v])f[v]=f[v-w[i]]+c[i];
       printf("%d\n",f[m]);
       return 0;/*10 4
2 1
3 3
4 5
7 9*/
}

#include<cstdio>
using namespace std;
const int maxm=201,maxn=31;
int m,n;
int w[maxn],c[maxn];
int f[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=w[i];v<=m;v++)//可以逐渐填入一个w[i],两个w[i]······
           if(f[v-w[i]]+c[i]>f[v])f[v]=f[v-w[i]]+c[i];
       printf("%d\n",f[m]);
       return 0;/*10 4
2 1
3 3
4 5
7 9*/
}

#include<cstdio>
using namespace std;
int v[6002],w[6002],c[6002];
int f[6002];
int n,m;
int max(int x,int y){
	if(x<y)return y;
	else return x;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%d%d%d",&v[i],&w[i],&c[i]);
	for(int i=1;i<=n;i++)
		for(int j=m;j>=0;j--)
			for(int k=0;k<=c[i];k++)
			{	if(j-k*v[i]<0)break;
                f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
             }
             printf("%d",f[m]);
            return 0;
}
/*5 1000
80 20 4
40 50 9
30 50 7
40 30 6
20 20 1*/

index = 0;
for (int i = 1; i <= m; i++) {
  int c = 1, p, h, k;
  cin >> p >> h >> k;
  while (k > c) {
    k -= c;
    list[++index].w = c * p;
    list[index].v = c * h;
    c *= 2;
  }
  list[++index].w = p * k;
  list[index].v = h * k;
}

for (循环物品种类) {
  if (是 0 - 1 背包)
    套用 0 - 1 背包代码;
  else if (是完全背包)
    套用完全背包代码;
  else if (是多重背包)
    套用多重背包代码;
}