题意描述：
给定一定数量的不同面值的钞票，输出由这些钞票组成的不超过出款上限（题目中的cash）的最大金额。
01背包问题，请参阅：
http://www.cppblog.com/hoolee/archive/2012/08/14/187179.html这里我想多说一句，本题中背包的容量是题中给的cash，每件物品的花费就是该钞票的面值，物品的价值也是该种钞票的面值，这里的花费和价值是一样的。
以下是本题代码：
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LENND 20
#define LENF 100010
typedef struct
{
int v;
int amt;
}Cash;
Cash cs[100];
int f[LENF];
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
int main()
{
int i, j;
int cash, N;
int n[LENND], D[LENND];
while(scanf("%d", &cash) != EOF)
{
scanf("%d", &N);
for(i = 0; i < N; i++)
scanf("%d%d", &n[i], &D[i]);
int count = 1;
for(i = 0; i < N; i++)
{
int M = n[i];
int t = 1;
while(M - t > 0)
{
cs[count].v = D[i];
cs[count++].amt = t;
M -= t;
t *= 2;
}
if(M != 0)
{
cs[count].v = D[i];
cs[count++].amt = M;
}
}
memset(f, 0, sizeof(f));
for(i = 1; i < count; i++)
{
int allv = cs[i].amt * cs[i].v;
for(j = cash; j >= allv; j--)
f[j] = Max(f[j], f[j - allv] + allv);
}
printf("%d\n", f[cash]);
}
//system("pause");
}
posted on 2012-08-14 17:33
小鼠标 阅读(204)
评论(0) 编辑 收藏 引用 所属分类:
DP