Onway

pku 2063 容量可变的完全背包

题意：
某人有一大笔资金s(s<1000000)，想通过购买债券获利。现有n(n<=10)种债券可买。已知每种债券购买金额w(1000的倍数)和一年后的获利v(不多于购买金额的10%)。可以将每年得到的所有获利都再次投入。问t(t<=40)年后，该人共有多少钱。

看懂题目的第一感觉是没思路，在网上找别的完全背包，找不到了，只能去想这个题。

当时的第一思路是每年获利后都做一次完全背包。至于状态压缩，是将原有资金和购买金额都除以1000，获利不变。每次背包后，都将最大获利除以1000，加到原有资金里（用double型）。
过了样例，提交返回了多次RE。看discuss说数组开小了。为了验证的却是数组越界的错误，一下狠心数组开大了两个数量级。
这下不是RE了，是WA。还是PKU比HDU厚道一点，数组访问越界是报RE，不是WA。

我觉得我是完全看懂了题意，是跟着题意写的代码，而且一次过了样例，这说明思路没错啊。在这种情况下，是可以少测别的数据吧，最多就是测一下边界数组。而直觉告诉我，边界是没问题的。

我怀疑状态压缩出乱子了（没试过压缩的），就干脆不压了，每次RE后都加大数组，一直到MLE。然后编译选错，又来了几个CE。盼星星盼月亮就是盼不到一个AC。
上网查看别人的代码，发现思路跟我的好像不一样。而且都不像我那样，用到double型。我也去掉double类型，将获利先加到总金额，在除以1000赋值给整形。这下提交终于看到AC了。

虽然AC了，但还是有三个地方是不懂得。

1，为什么数组要开到46000呢。
假设将所有资金都能获得最大获利，那么40年后，就是：
1 000 000*(1.1^40)=45259255.568175951805889356034897
2,为什么我用double的时候会出错呢？
其实现在还是不懂，估计也就是有精度损失。
3，别人的思路为什么只求一次完全背包，就的了呢？
由于可以知道40年后的最大金额，不超过46000（压缩后），一次背包后，就能得出每一金额的最大获利。然后每一年获利后都加进去，直接提取出来就可以再次求获利。

 1#include <iostream>
 2#include <algorithm>
 3using namespace std;
 4const int MAX=46000;
 5int dp[MAX],w[12],v[12];
 6int fmax(int a,int b)
 7{return a>b?a:b;}
 8int main()
 9{
10    int t;
11    scanf("%d",&t);
12    while(t--)
13    {
14        int money,year,bond,i,j,sum;
15        scanf("%d%d%d",&money,&year,&bond);
16        for(i=1;i<=bond;++i)
17        {
18            scanf("%d%d",&w[i],&v[i]);
19            w[i]/=1000;
20        }
21
22        memset(dp,0,sizeof(dp));
23        for(i=1;i<=bond;++i)
24            for(j=w[i];j<=MAX-1;++j)
25                dp[j]=fmax(dp[j],dp[j-w[i]]+v[i]);
26
27        while(year--)
28        {
29            sum=money/1000;
30            money+=dp[sum];
31        }
32        printf("%d\n",money);
33    }
34    return 0;
35}