POJ 2063 -- Investment

2063 -- Investment

John never knew he had a grand-uncle, until he received the notary's letter. He learned that his late grand-uncle had gathered a lot of money, somewhere in South-America, and that John was the only inheritor.
John did not need that much money for the moment. But he realized that it would be a good idea to store this capital in a safe place, and have it grow until he decided to retire. The bank convinced him that a certain kind of bond was interesting for him.
This kind of bond has a fixed value, and gives a fixed amount of yearly interest, payed to the owner at the end of each year. The bond has no fixed term. Bonds are available in different sizes. The larger ones usually give a better interest. Soon John realized that the optimal set of bonds to buy was not trivial to figure out. Moreover, after a few years his capital would have grown, and the schedule had to be re-evaluated.
Assume the following bonds are available:

Value	Annual interest
4000 3000	400 250

With a capital of e10 000 one could buy two bonds of $4 000, giving a yearly interest of $800. Buying two bonds of $3 000, and one of $4 000 is a better idea, as it gives a yearly interest of $900. After two years the capital has grown to $11 800, and it makes sense to sell a $3 000 one and buy a $4 000 one, so the annual interest grows to $1 050. This is where this story grows unlikely: the bank does not charge for buying and selling bonds. Next year the total sum is $12 850, which allows for three times $4 000, giving a yearly interest of $1 200.
Here is your problem: given an amount to begin with, a number of years, and a set of bonds with their values and interests, find out how big the amount may grow in the given period, using the best schedule for buying and selling bonds.

Input

The first line contains a single positive integer N which is the number of test cases. The test cases follow.
The first line of a test case contains two positive integers: the amount to start with (at most $1 000 000), and the number of years the capital may grow (at most 40).
The following line contains a single number: the number d (1 <= d <= 10) of available bonds.
The next d lines each contain the description of a bond. The description of a bond consists of two positive integers: the value of the bond, and the yearly interest for that bond. The value of a bond is always a multiple of $1 000. The interest of a bond is never more than 10% of its value.

Output

For each test case, output – on a separate line – the capital at the end of the period, after an optimal schedule of buying and selling.

Sample Input

1  10000 4  2  4000 400  3000 250

Sample Output

14050

The value of a bond is always a multiple of $1 000.利用这点可大大降低复杂度。
典型的完全背包， 因为每种股票的数量无限， 只要你有足够的钱就可以买到任意的股票。
就可以从第一年起一直每年算一次完全背包得到当年年终的钱，
再第二年依次算到第y年， 前一年的钱可以算作是当年的本钱。
但是如果不加任何优化会超时， 注意到股票的价值是1000的倍数，
所以可以是股票的价值都除以1000， 相应的本金也除以1000， 于是循环次数就大大的减少了。
http://www.cnblogs.com/freezhan/archive/2012/08/15/2974245.html

完全背包状态转移方程：

for i=1..N

    for v=0..V

        f[v]=max{f[v],f[v-cost]+weight}

注意：转换 本题的背包容量就是本金

            但是每一年都有利息产生，所以本金都会增长，从而背包的体积不断增大。

            放入背包的物品的容量就是每种利息所需的本金cost[i]，放入物品后产生的价值就是  

           利息weight[i]。

内存问题：注意题目中的本金很大但是最开始最多的本金不超过$1 000 000

                     而且每种计算利息所需的本金都是$1 000的倍数，所以为了避免超内存，每次  

                     dp时先把本金除以$1 000，相应的cost也除以$1 000

那么dp数组到底开多大才合适呢，题中说最多存40年，开始时本金不超过$1 000 000而每次的利息又不会超过本金的 10% ，

所以 数组的大小应该是 $1 000 000 / 1000 * ( 1.1 ) ^40

而 1.1^40 大概为 45.259256，就取 50 吧。

从而数组开 1 000 * 50 = 50 000

1.     while(T--)  
2.     {  
3.         scanf("%d%d", &V, &year);  
4.           
5.         int Max = V;  
6.           
7.         scanf("%d", &n);  
8.         for(int i = 1; i <= n; i++)  
9.         {  
10.             scanf("%d%d", &cost[i], &weight[i]);  
11.             cost[i] /= 1000; //每种债券除以1000减少内存。  
12.         }  
13.           
14.         while(year--)  
15.         {  
16.             V /= 1000; //相应的每次的本金除以1000减少内存  
17.             memset(dp, 0, sizeof(dp));  
18.             for(int i = 1; i <= n; i++)  
19.             {  
20.                 for(int j = cost[i]; j <= V; j++)  
21.                     dp[j] = max(dp[j], dp[j-cost[i]] + weight[i]);  
22.             }  
23.               
24.             Max += dp[V]; //本金+利息(注意利息开始没有除以也不用除以1000,所以Max即为所求)  
25.             V = Max;  
26.         }  
27.           
28.         printf("%d\n", V);  
29.     }  

http://www.xuebuyuan.com/1847469.html
http://laiba2004.blog.163.com/blog/static/88351202201371683937559/
不必每一年都进行一次完全背包计算，容量V虽然每年都有变化，但是最大的容量值不变，所以按照最大的容量值进行完全背包，最后再根据每年的容量求结果.
//不必每一年都进行一次完全背包计算，容量V虽然每年都有变化，但是最大的容量值不变， //所以按照最大的容量值进行完全背包，最后再根据每年的容量求结果。 void comp(int cost ,int weight ) { int v; for(v=cost;v<=summ;v++) { if(v-cost>=0) dp[v]=maxx(dp[v],dp[v-cost]+weight); } } scanf("%d%d",&sum,&m); scanf("%d",&n); for(i=0;i<n;i++) { scanf("%d%d",&a[i],&b[i]); } //这里是开始改动的部分 summ=sum; for(i=0;i<m;i++) summ=1.1*summ; summ=summ/1000; //直接summ=60000;也可以的 for(i=0;i<n;i++) { comp(a[i]/1000,b[i]); } for(i=0;i<m;i++) sum+=dp[sum/1000]; printf("%d\n",sum);
Read full article from 2063 -- Investment