完全背包问题

Problem Description

设有n种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为m，今从n种物品中选取若干件(用一个物品可以多次选取)，使其重量的和小于等于m，而价值的和为最大。

Input

输入有多组数据，对于每组输入数据第1行：两个整数，M(背包容量,M<=200)和N(物品数量,N<=30);
第2行至N+1行：每行两个整数Wi,Ci，表示每个物品的重量和价值。

Output

对于每组输入输出一个数，表示最大总价值。

Sample Input

10 4
2 1
3 3
4 5
7 9

Sample Output

max=12

//  二维数组
#include<stdio.h>
int w[35],c[35],f[35][205];
int main()
{
   int m,n,i,v;
    while(scanf("%d%d",&m,&n)!=EOF)  // m背包容量，n 物品数
	{  
		for(i=1;i<=n;i++)
			scanf("%d%d",&w[i],&c[i]);
       // f[i][v]表示前i件物品，总重量不超过v的最优价值

		for(i=1;i<=n;i++)
			for(v=1;v<=m;v++)    // v=1--m 这样每件物品可以选无限件 
	            if(w[i]>v)  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\n",f[n][m]);  // 最有价值

		for(i=0;i<=n;i++)
			for(v=0;v<=m;v++)
				f[i][v]=0;
	}
 return 0;
}




//  一维数组
#include<stdio.h>
int main()
{
	int w[35],c[35],f[205],i,v,m,n;
   while(scanf("%d%d",&m,&n)!=EOF)
   {
      for(i=1;i<=n;i++)
		  scanf("%d%d",&w[i],&c[i]);
	  for(i=1;i<=n;i++)
		  for(v=w[i];v<=m;v++)
			  if(f[v]<f[v-w[i]]+c[i])  f[v]=f[v-w[i]]+c[i];
	  printf("max=%d\n",f[m]);
	  for(i=0;i<=m;i++)
		  f[i]=0;
   }

  return 0;
}