算法：poj 2063 Investment （dp 完全背包）

算法：poj 2063 Investment （dp 完全背包）2014-01-10 csdn shuangde800题目大意：

有n种债券可以买，每种的价钱分别为a（a是1000的倍数），每年利息为b 。某个人共有钱tot（tot是1000的倍数），问他在y年后，最多可以有多少钱？

思路：

由于tot和a都是 1000的倍数，所有在计算时可以把他们缩小1000倍，这样节约内存和时间。

按照贪心的思想，每一年都用完全背包求出这一年最大可以得到的利息，然后下一年再用加上利息后的总钱继续计算下去……

代码：

#include<iostream>#include<queue>#include<stack>#include<cstdio>#include<cstring>#include<cmath>#include<map>#include<set>#include<string>#define MP make_pair#define SQ（x） （（x）*（x））typedef int int64;const double PI = acos（-1.0）;const int INF = 0x3f3f3f3f;using namespace std;const int MOD = 1000000007;const int MAXN = 13;const int ADD = 1000*100;int tot, y,n;int c[MAXN], w[MAXN];int f[100030];int main（）{int nCase;scanf（"%d", &nCase）;while（nCase--）{scanf（"%d%d%d", &tot, &y, &n）;for（int i=0; i<n; ++i）{scanf（"%d%d", &c[i], &w[i]）;c[i] /= 1000;}for（int i=0; i<y; ++i）{for（int j=0; j<=tot/1000; ++j）f[j] = 0;for（int j=0; j<n; ++j）{for（int v=c[j]; v<=tot/1000; ++v）f[v] = max（f[v], f[v-c[j]]+w[j]）;}tot += f[tot/1000];}printf（"%d
", tot）;}return 0;}