POJ 2063 Investment(完全背包)_happysnow_新浪博客

POJ 2063 Investment(完全背包)_happysnow_新浪博客

大意：先有money元钱，kinds支股票
     每支股票信息为（cost,w）即存储cost购买一支该股票，一年后返回cost+w元钱
  money,cost均为1000的整数倍
  现问year年后，最多能达到多少现金？
  分析：
  典型的完全背包， 因为每种股票的数量无限， 只要你有足够的钱就可以买到任意的股票。
    就可以从第一年起一直每年算一次完全背包得到当年年终的钱，
 再第二年依次算到第y年， 前一年的钱可以算作是当年的本钱。
 但是如果不加任何优化会超时， 注意到股票的价值是1000的倍数，
 所以可以是股票的价值都除以1000， 相应的本金也除以1000， 于是循环次数就大大的减少了。

Read full article from POJ 2063 Investment(完全背包)_happysnow_新浪博客