本文共 813 字，大约阅读时间需要 2 分钟。

先做完这几种类型背包的题再总结。这道题是多次运用背包问题，每次都要去挑背包，且背包越来越大。

#include
   
    #include
    
     #include
     
      #include
      
       const int N = 1e7;using namespace std;int w[15], v[15];int dp[N];int main(){    int N; cin >> N;    while (N--)    {        int W1,W2, year;        cin >> W1 >> year;//W1代表原始的重量，就是本金。        int n;      //n个物品        cin >> n;        for (int i = 1; i <= n; i++)        {            cin >> w[i] >> v[i];            w[i] = w[i] / 1000;        }        for (int i = 0; i < year; i++)        {            W2 = W1 / 1000;            fill(dp, dp + W2+1, 0);            for (int j = 1; j <= n; j++)                for (int k = w[j]; k <= W2; k++)                    dp[k] = max(dp[k], dp[k - w[j]] + v[j]);            W1 += dp[W2];           }        cout << W1 << endl;    }    system("pause");}
      
     
    
   

转载地址：http://jkyci.baihongyu.com/