POJ 2063 Investment【クラシック完全リュックサック】
DPバックパック（メモリの変換を減らすことに注意）
クイックリンク:http://poj.org/problem?id=2063
CSUST 2012年夏休み8月にチームを組んでから8回目の個人戦：http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=11473#problem/D
Investment
Time Limit: 1000 MS
メモリLimit: 30000 K
Total Submissions: 5370
Acceepted: 1848
Description
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-Amerrica，and that Johm the nitor.
John did not need that much 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 convincend hite bortine of。
This kid of bond has a fixed value、and gives a fixed amountof yeararlyinterest、payed to the owner the the the the end of each year.The bond hasのfixed term.Bonds arararararararare avavavlalable e e e e e inininlalalable e e e ininindidifferentindifferentsizininininininininininindededededededededededededededededesizzzzzzzininininininininininininininininininininininininininininininininininininto figure out.Moreover，after a few years capital would have grown、and the schedule had to be re-evaluated.
Asume the follwing bonds are available:
Value
Annual interest
4000,000
400 250
With a capital of e 10 000 one could buy two bonds of$4 000、ギヴィングa yearly interest of$800.Buying two bonds of$3 000、and one of$4 000 is a better idea、as it gives a yearlyinterest of$900.After tyears。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$
Here is your proble m：given an amount to begin with、a number of years、and a set of bonds their values and interests、find out how the amount magy grow in the given period、using the best hedule bolling.
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)、and the number of years the capital may grow(at most 40)
The follwing line contains a single number:the number d(=d==10)of available bonds.
The next d lineach 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
Output
For each test case，output–on a separate line–the capital the end of the period，after an optimal schedule of buying and selling.
Sample Input
Northwester n Europe 2004
下のは前に書いたものです。今はDPをもう一度書き直しました。
件名:
まず整数を入力します。 T ，あります T グループテストデータ
元金を貸してあげます V 銀行振り込みの年限 year ( つまり、サンプルの2行目に入力したデータです。 )
次に整数を入力します。 n あります n 年利計算法
残りの n 銀行とは元金ごとに発生する年利のお金です。
アルゴリズムの考え：完全リュックサックの2番目の基本的なバックパックの問題モデルは、アイテムごとに何度も無限に置くことができます。PS：もし何か分からないなら、完全リュックサックを見てください。
http://blog.csdn.net/cfreezhan/article/details/7865136#_P 02:_完全リュックサック問題
完全バックパック状態移行方程式：
for i=1.N
for v=0.V
f[v]=max｛f[v]，f[v-cost]+weight｝
注意：変換 本题のリュックの容量は元本です。
しかし、毎年利息が発生しますので、元金は増加します。
リュックサックに入れるものの容量は利息ごとに必要な元金のコスプレです。
利息weight[i]
メモリの問題：問題の中の元金が大きいことに注意しますが、一番最初に多い元金は$1を超えません。 000 000
しかも利息を計算するために必要な元金は全部$1です。 000の倍数ですので、メモリオーバーを避けるために毎回
dpの時は元金を$1で割ります。 000、対応するcosも$1で割っています。 000
では、dp配列は一体どれぐらいの大きさで開けたらいいですか？問題の中では最大40年間貯金します。開始時の元金は$1を超えません。 000 万円の利息は元金を超えません。 10% ，
だから 配列のサイズは $1 000 000 / 1000 * ( 1.1 ) ^40
に対する 1.1^40 大体 45.259256,取ります 50 でしょう
を選択します 1 000 * 50 = 50 000
ポイント：メモリの処理に関しては、ゲーム中ずっと間違っています。メモリがちゃんと処理されていません。
先輩の問題を見ました。http://www.shabiyuan.com/?categoryいらっしゃいませ
やっと分かりました。具体的な分析は下記のコードエリアを参照してください。
クイックリンク:http://poj.org/problem?id=2063
CSUST 2012年夏休み8月にチームを組んでから8回目の個人戦：http://acm.hust.edu.cn:8080/judge/contest/view.action?cid=11473#problem/D
Investment
Time Limit: 1000 MS
メモリLimit: 30000 K
Total Submissions: 5370
Acceepted: 1848
Description
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-Amerrica，and that Johm the nitor.
John did not need that much 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 convincend hite bortine of。
This kid of bond has a fixed value、and gives a fixed amountof yeararlyinterest、payed to the owner the the the the end of each year.The bond hasのfixed term.Bonds arararararararare avavavlalable e e e e e inininlalalable e e e ininindidifferentindifferentsizininininininininininindededededededededededededededededesizzzzzzzininininininininininininininininininininininininininininininininininininto figure out.Moreover，after a few years capital would have grown、and the schedule had to be re-evaluated.
Asume the follwing bonds are available:
Value
Annual interest
4000,000
400 250
With a capital of e 10 000 one could buy two bonds of$4 000、ギヴィングa yearly interest of$800.Buying two bonds of$3 000、and one of$4 000 is a better idea、as it gives a yearlyinterest of$900.After tyears。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$
Here is your proble m：given an amount to begin with、a number of years、and a set of bonds their values and interests、find out how the amount magy grow in the given period、using the best hedule bolling.
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)、and the number of years the capital may grow(at most 40)
The follwing line contains a single number:the number d(=d==10)of available bonds.
The next d lineach 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
Output
For each test case，output–on a separate line–the capital the end of the period，after an optimal schedule of buying and selling.
Sample Input
1
10000 4
2
4000 400
3000 25014050Northwester n Europe 2004
下のは前に書いたものです。今はDPをもう一度書き直しました。
件名:
まず整数を入力します。 T ，あります T グループテストデータ
元金を貸してあげます V 銀行振り込みの年限 year ( つまり、サンプルの2行目に入力したデータです。 )
次に整数を入力します。 n あります n 年利計算法
残りの n 銀行とは元金ごとに発生する年利のお金です。
アルゴリズムの考え：完全リュックサックの2番目の基本的なバックパックの問題モデルは、アイテムごとに何度も無限に置くことができます。PS：もし何か分からないなら、完全リュックサックを見てください。
http://blog.csdn.net/cfreezhan/article/details/7865136#_P 02:_完全リュックサック問題
完全バックパック状態移行方程式：
for i=1.N
for v=0.V
f[v]=max｛f[v]，f[v-cost]+weight｝
注意：変換 本题のリュックの容量は元本です。
しかし、毎年利息が発生しますので、元金は増加します。
リュックサックに入れるものの容量は利息ごとに必要な元金のコスプレです。
利息weight[i]
メモリの問題：問題の中の元金が大きいことに注意しますが、一番最初に多い元金は$1を超えません。 000 000
しかも利息を計算するために必要な元金は全部$1です。 000の倍数ですので、メモリオーバーを避けるために毎回
dpの時は元金を$1で割ります。 000、対応するcosも$1で割っています。 000
では、dp配列は一体どれぐらいの大きさで開けたらいいですか？問題の中では最大40年間貯金します。開始時の元金は$1を超えません。 000 万円の利息は元金を超えません。 10% ，
だから 配列のサイズは $1 000 000 / 1000 * ( 1.1 ) ^40
に対する 1.1^40 大体 45.259256,取ります 50 でしょう
を選択します 1 000 * 50 = 50 000
//Accepted 360 KB 79 ms C++ 667 B 2013-03-14 19:26:23
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 50 * 1000;
int dp[maxn];
int main()
{
int T;
int V, year;
int n;
int cost[11], weight[11];
scanf("%d", &T);
while(T--)
{
scanf("%d%d", &V, &year);
int Max = V;
scanf("%d", &n);
for(int i = 1; i <= n; i++)
{
scanf("%d%d", &cost[i], &weight[i]);
cost[i] /= 1000; // 1000 。
}
while(year--)
{
V /= 1000; // 1000
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
{
for(int j = cost[i]; j <= V; j++)
dp[j] = max(dp[j], dp[j-cost[i]] + weight[i]);
}
Max += dp[V]; // + ( 1000, Max )
V = Max;
}
printf("%d
", V);
}
return 0;
}ポイント：メモリの処理に関しては、ゲーム中ずっと間違っています。メモリがちゃんと処理されていません。
先輩の問題を見ました。http://www.shabiyuan.com/?categoryいらっしゃいませ
やっと分かりました。具体的な分析は下記のコードエリアを参照してください。
//AC 948k 94ms C++ POJ 2063 Investment
/* :DPz ( 《 》 ， hdu 1114)
: N 。
:if(dp[j]<dp[j-value[i]]+interest[i])
dp[j]=dp[j-value[i]]+interest[i];
， 。
， ， 。
: , , (http://www.shabiyuan.com/?category ) 。
， 。 dp , 1000 ， 1000
*///400k 63ms ( maxn=60000 )#include<cstdio>
#include<cstring>
const int maxn=200000;
int dp[maxn];
int main()
{
int test;
int start,year;
int d;
int i,j;
int value[15],interest[15];
int ans,max;
scanf("%d",&test);
while(test--)
{
scanf("%d%d",&start,&year);
ans=max=start;
scanf("%d",&d);
for(i=0;i<d;i++)
{
scanf("%d%d",&value[i],&interest[i]);
value[i]/=1000;// 1000 。
}
while(year--)
{
memset(dp,0,sizeof(dp));
max/=1000; // 1000
for(i=0;i<d;i++)
for(j=value[i];j<=max;j++)
if(dp[j]<dp[j-value[i]]+interest[i])
dp[j]=dp[j-value[i]]+interest[i];
ans+=dp[max];// + ( 1000, ans )
max=ans;
}
printf("%d
",ans);
}
return 0;
}