首页 > 代码库 > poj2063投资--完全背包

poj2063投资--完全背包

题意:

有d种股票,每种股票有一个购买钱数,和收益,你有本金C,year年之后,可以获得最大的投资收益是多少?

分析:

那么这里,我们可以知道每种股票可以购买无限次,那么这里可以看出是完全背包问题,可以把本金C看做背包。但是需要处理一下(等会说这个问题)

我们单独看看一年的收益,分析dp过程:

dp[i][j] 表示考虑第i种股票,使用j 这么多钱的时候的最大收益。通过之前的 白话背包之完全背包 我们可以了解这里可以优化为一维数组

但是考虑到dp数组不能太大,同时股票售价都是1000的倍数,我们需要处理的就是在这里每次金额 除以 1000

同时,对于每一年,我们完全背包一次获取最大利益,然后将所有金额再给下一年完全背包

上马:

//
#include <stdio.h>
#include <string.h>

#define MAX 50005

int N;//案例
int d;//股票套数
int V[11],In[11];//价值利息
int ans[MAX];//dp数组

int dp(int pre)
{
    memset(ans,0,sizeof(ans));
    for(int i = 1; i <= d; i ++)
    {
        for(int j = V[i]; j <= pre; j ++)
        {
            ans[j] = ans[j]>ans[j-V[i]]+In[i] ? ans[j]:ans[j-V[i]]+In[i];
        }
    }
    return ans[pre];
}

int main()
{
    int C,year;//开始资金
    scanf("%d",&N);
    while(N--)
    {
        scanf("%d%d%d",&C,&year,&d);
        for(int i = 1; i <= d; i ++)
        {
            scanf("%d%d",&V[i],&In[i]);
            V[i] /= 1000;
        }
        for(int i = 1; i <= year; i ++) //多次完全背包
        {
            C += dp(C/1000);
        }
        printf("%d\n",C);
    }
    return 0;
}
/*
1
10000 4
2
4000 400
3000 250
*/