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}