全然背包问题。
我的背包训练第二题。依照背包九讲的步骤来搞。
题意是说给你一些本钱，然后有一些债券能够购买。不同的债券会有不同的利润，在规定年限内，利润要最大。
债券是无限制购买的，（全然背包）获得的利润能够买债券，（背包变大）
每年都能够选择债券，也就是每年都要又一次開始，（每年一次）
最后得出你手上的钱有多少。这道题题目中提示了 1000的倍数。
可是本钱不一定，利润也不一定。
仅仅有债券在输入时候能够除1000。每年開始的时候，本钱除1000。只是也要保存 %1000。
02（笑）背包的自我修养：
F[0…V ] ← 0
for i ← 1 to N
for v ← Ci to M
F[v] ← max(F[v]; F[v - Ci] +Wi)
伪代码，跟01背包有点相似。也有点不同。
C[]表示费用，W[]表示价值。M表示背包容量
01背包的第二个过程是反过来的，从M → 0。为了保证在考虑“选入第i 件物品”这件
策略时，根据的是一个绝无已经选入第i 件物品的子结果F[i - 1; M - Ci]。
全然背包却可能某种物品选择多次。
int dp[1000001];
int c[100001],v[100001];
memset(dp,0,sizeof(dp));
for(int i=0;i<n;i++)
{
for(int j=c[i];j<=m;j++)
dp[j]=max(dp[j],dp[j-c[i]]+v[i]);
}
已经坑到第二步，全然背包了。只是还得细细体会。
本题代码：
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<queue>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<cmath>
#define INF 0x7fffffff
#define eps 1e-6
using namespace std;
int dp[100001];
int c[11],v[11];
int main()
{
int t,m,n,year;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&year);
scanf("%d",&m);
for(int i=0; i<m; i++)
{
scanf("%d%d",&c[i],&v[i]);
c[i]/=1000;
}
memset(dp,0,sizeof(dp));
while(year--)
{
int tmp=n%1000;
n/=1000;
for(int i=0; i<m; i++)
{
if(c[i]>n)continue;
for(int j=c[i];j<=n;j++)
{
dp[j]=max(dp[j],dp[j-c[i]]+v[i]);
}
}
int ans=0;
for(int i=0; i<=n; i++)
ans=max(ans,dp[i]);
n=n*1000+tmp+ans;
}
printf("%d
",n);
}
}