算法：poj 2063 Investment (dp 完全背包)

题目大意：

有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\n", tot);
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索int
， include
， 背包问题
， const
， 贪心算法
， n年后
贪心算法的题目
背包dp、dp背包问题、双色球2063期、c 2063、hdu2063，以便于您获取更多的相关知识。