首页 > 代码库 > 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 */
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。