给你钱数，还有年数year，还有多少钱一年多少利息，问几年后最多的钱数（利息算到下一年的本金中）。
等于求year次完全背包，完全背包外面再套层循环即可。
钱初始值最大为100W。。。本来我想，开个100W的背包。写完了，一直RE，在ZOJ上是SE，表示郁闷啊。
在poj上看了讨论版的，我郁闷了！100W是初始值啊，后面利息加上的话 = =。。。算算。。最多10%。。100W+100W*0.1+....，这个这个数。。我算算。。。是45259172。。。我刚编了个程序算出来的。做的时候看讨论版知道这个数了。。。
因为投资的钱都是1000的倍数，所以本金，投资的钱数除以1000再计算利息后再加上没除1000的本金再算下一个，这样的话，背包的容量就大大缩小了！
- #include <stdio.h>
- #include <stdlib.h>
- #include <iostream>
- #include <string.h>
- using namespace std;
- int money[45001];
- int main(void)
- {
- int ncases,n,year,c;
- int w[11],v[11],temp;
- cin >> ncases;
- while( ncases-- )
- {
- cin >> c >> year >> n;
- for(int i=0; i<n; i++)
- {
- cin >> w[i] >> v[i];
- w[i] /= 1000;
- }
- temp = c;
- for(int i=0; i<year; i++)
- {
- c = temp;
- c /= 1000;
- for(int k=0; k<=c; k++)
- money[k] = 0;
- for(int k=0; k<n; k++)
- for(int j=w[k]; j<=c; j++)
- money[j] = max(money[j-w[k]]+v[k],money[j]);
- temp += money[c];
- }
- cout << temp << endl;
- }
- return 0;
- }
-
另附python版的程序：
#POJ2063 Investment def SolveInvestment(): W=12850 D=4 N=2 V=[4,3] I=[400,250] def DP(W): W=int(W/1000) DP=[[0 for i in range(W+1)]for j in range(N+1)] for i in range(1,N+1): K=int(floor(W/V[i-1])) for w in range(W+1): for k in range(1,K+1): # print DP[i][w],"-->", if DP[i-1][w-k*V[i-1]]+k*I[i-1]>DP[i][w]: if w-k*V[i-1]>=0: DP[i][w]=DP[i-1][w-k*V[i-1]]+k*I[i-1] # print i-1,w-k*V[i-1],DP[i-1][w-k*V[i-1]],"+",k,I[i-1] # print DP[i][wb] return DP[N][W] for year in range(D): print "Year",year+1,":",W,"->", Int=DP(W) W+=Int print W return