题意描述：有几种不同的债券共购买，每种债券有相应的年效益，这些债券每年可以兑现一次，并且没有任何手续费，兑现后可以选择购买不同债券。给定初始金额和年限，求出最终的最大收益。
解题思路：每年按01背包问题计算一遍即可。
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define LEN 100000
typedef struct
{
int w;
int i;
}Bonds;
int f[LEN];
Bonds bd[20];
int Max(int a, int b)
{
if(a > b)
return a;
return b;
}
int main()
{
int i, j, k;
int N;
int M, Y;
int d, a, b;
scanf("%d", &N);
while(N--)
{
scanf("%d%d", &M, &Y);
scanf("%d", &d);
for(i = 1; i <= d; i++)
{
scanf("%d%d", &bd[i].w, &bd[i].i);
bd[i].w /= 1000;//债券的面值都是1000的整数倍
}
int alli = 0;
for(j = 0; j < Y; j++)
{
M += alli;
int P = M / 1000;//债券的面值都是1000的整数倍
memset(f, 0, sizeof(f));
for(i = 1; i <= d; i++)
for(k = bd[i].w; k <= P; k++)
f[k] = Max(f[k], f[k - bd[i].w] + bd[i].i);
alli = f[P];
}
M += alli;
printf("%d\n", M);
}
//system("pause");
}
posted on 2012-08-14 11:45
小鼠标 阅读(210)
评论(0) 编辑 收藏 引用 所属分类:
DP