題意描述：
給定一定數量的不同面值的鈔票，輸出由這些鈔票組成的不超過出款上限（題目中的cash）的最大金額。
01背包問題，請參閱：
http://m.shnenglu.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
小鼠標 閱讀(225)
評論(0) 編輯 收藏 引用 所屬分類:
DP