DP：zoj 2224 || poj 2063 Investment（完全背包）
[转]http://blog.csdn.net/zxy_snow/article/details/6021316?
等于求year次完全背包，完全背包外面再套层循环即可。
#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;
}
