首页 > 代码库 > poj2063 Investment

poj2063 Investment

2024-07-15 10:54:51   220人阅读

 

http://poj.org/problem?id=2063

首先总结一下：总的来说通过这题我深深感觉到了自己的不足，比赛时思维很受限，。。。面对超时，没有想到好的解决方案。

题意：给出初始资金，还有年数，然后给出每个物品的购买价格与每年获得的利益，要求在给出的年份后所能得到的最大本利之和。

思路：因为每种物品可以多次购买，可以看做是完全背包的题目，但是要注意的是，由于本金可能会很大，所以我们要对背包的大小进行压缩，（否则超时超内存）值得注意的是，题目已经说了本金与物品的购买价格都是1000的倍数，所以我们可以将他们都除以1000来进行压缩，然后就是一道完全背包模板题了。

解决方案：完全背包问题，因为每种股票可以无限投资，而问n年之后的最大收益，我们将每一年的最大收益计算，将前i-1年的现有收益作为现在投资金额再次对第i年进行投资。

#include <iostream>#include <stdio.h>#include <string.h>#include <stdlib.h>#include <math.h>int dp[1000001];int main(){    int T,V,time,d,VV;//V是背包的容积，w[i]是物品的体积    int w[12],v[12];    scanf("%d",&T);    while(T--)    {       scanf("%d%d",&V,&time);       scanf("%d",&d);       VV=V;       for(int i=1;i<=d;i++)       {           scanf("%d%d",&w[i],&v[i]);           w[i]=w[i]/1000;//因为证券都是1000的倍数       }       for(int i=1;i<=time;i++)       {           V=VV/1000;//因为证券都是1000的倍数，钱数不满整千绝对不能买，所以完全可以/1000           for(int j=0;j<=V;j++)              dp[j]=0;           for(int j=1;j<=d;j++)           {               for(int k=w[j];k<=V;k++)               {                   if(dp[k]<dp[k-w[j]]+v[j])                   {                       dp[k]=dp[k-w[j]]+v[j];                   }               }           }           VV=VV+dp[V];//钱数累加       }       printf("%d\n",VV);    }    return 0;}

 


联系
我们