題意描述：有幾種不同的債券共購買，每種債券有相應的年效益，這些債券每年可以兌現一次，并且沒有任何手續費，兌現后可以選擇購買不同債券。給定初始金額和年限，求出最終的最大收益。
解題思路：每年按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
小鼠標 閱讀(220)
評論(0) 編輯 收藏 引用 所屬分類:
DP