DP：zoj 2224 || poj 2063 Investment（完全双肩包）

DP：zoj 2224 || poj 2063 Investment（完全背包）

[转]http://blog.****.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;
}