这有一篇完全背包的详解，也加了判断是否恰好装满的状态传送门(Piggy-Bank)

       题意在代码注释中有，算是完全背包的模板题吧，但是需要注意一点，因为题目中说了所有数据都是1000的倍数，所以我们可以对数据都进行缩小1000倍来进行计算。


AC代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#define MAX(a,b) a>b?a:b
using namespace std;
const int MAXN = 100000;    // 数组不要开的太大，因为开的太大TLE了好多次
int dp[MAXN];
int val[15];
int w[15];
int T,n,m,y,sum;
int main()
{
  scanf("%d",&T);
  while(T--){
    scanf("%d%d",&sum,&y);
    scanf("%d",&m);
    for(int i=0;i<m;i++){
      scanf("%d%d",&val[i],&w[i]);
      val[i] /= 1000;        // 因为题上说了数据都能被1000除尽，所以在这里压缩一下
    }
    for(int i=0;i<y;i++){   // 因为有y年，所以需要循环y次
      memset(dp,0,sizeof(dp));  // 每次循环都需要初始化dp，记录每一年的值
      int s = sum/1000;     // 将本金也压缩
      for(int j=0;j<m;j++){    // 完全背包过程
        for(int k=val[j];k<=s;k++){
          dp[k] = MAX(dp[k],dp[k-val[j]]+w[j]);
        }
      }
      sum += dp[s];    // 钱数+利息
    }
    printf("%d\n",sum);
  }
  return 0;
}
/***
  [来源] POJ 2063
  [题目] Investment
  [题意]
     银行存钱的问题，问怎样选择才能获得最大收益，先是输入本金，然后输入要存多少年，然后输入n行数据，一行
     数据两个值，一个是投资价格，一个是收益而已把本金当作背包容量，然后就是一个完全背包问题，唯一不同的是
     需要循环y年。
  [输入]
     1
     10000 4
     2
     4000 400
     3000 250
  [输出]
     14050
*/