转载地址：http://m.blog.csdn.net/blog/u010489766/9229011
题目链接：http://poj.org/problem?id=1276
题意：机器里面共有n种面额的钱币，每种各ni张，求机器吐出小于等于所要求钱币的最大值
解析1：这题大牛都用了多重背包，不过，我一同学想出了一种就这题而言特别简单有效的方 法。（话说我就认为这题本来就不需要用到背包的，因为n的范围只到10，太小了）。方法就是对钱进行遍历，看这些钱一共能组成多少面额的钱，然后从 cash向下枚举就行了。因为最多只有10*100000一百万的数据量而已。
//算法就是枚举，看0~cash的钱是不是都能到，到了是1，否则为0
#include<stdio.h>
#include<string.h> int cash,N,n[20],d[20],dp[100100];
int main()
{
while(scanf("%d",&cash) != EOF)
{
memset(n,0,sizeof(n));
memset(d,0,sizeof(d));
memset(dp,0,sizeof(dp));
int count = 0;
dp[0] = 1;
scanf("%d",&N);
for(int i = 1; i <= N ; i++)
scanf("%d%d",&n[i],&d[i]);
for(int i = 1; i <= N ; i++)
{
for(int k = cash; k >= 0 ; k--)//N的范围较小，所以直接枚举
{
if(dp[k] == 1)
{
for(int j = 1; j <= n[i] ; j ++)
{
if(k+j*d[i] <= cash)//不加的话可能会超出数组的范围
dp[k+j*d[i]] = 1;//此处可以直接等于1，因为更新k以上的，k以下的还是上一次的1
}
}
}
} for(int i = cash; i >= 0 ; i --)
if(dp[i] == 1)
{
printf("%d\n",i);
break;
}
}
return 0;
}
解析2：多重背包，把每种钱的张数按照二进制分开，例如13分为1,2,4,6,(之所以按照二进制是因为这么分的话，小于13任何数都可由1,2,4,6组合而成)，然后按照01背包搞定。
#include<stdio.h>
#include<string.h> int cash,n,v[10100],dp[101000];//数组要开的足够大
int main()
{
while(scanf("%d",&cash) != EOF)
{
memset(dp,0,sizeof(dp));
memset(v,0,sizeof(v));
scanf("%d",&n);
int cnt = 0;
for(int i = 1; i <= n ; i ++)
{
int a,b,t = 1;
scanf("%d%d",&b,&a);
if(b != 0)
{
while(t < b)//此处是把b按照二进制分开
{
b = b - t;
v[cnt++] = a * t;
t *= 2;
}
v[cnt++] = b*a;
}
}
if(n == 0 || cash == 0)
{
printf("0\n");
continue;
} dp[0] = 1;
for(int i = 0 ; i < cnt ; i ++)
for(int j = cash ; j >= v[i] ; j --)
dp[j-v[i]] == 1?dp[j] = 1:0; for(int i = cash; i >= 0;i--)
{
if(dp[i] == 1)
{
printf("%d\n",i);
break;
}
}
}
return 0;
}