为了挽救灾区同胞的生命，心系灾区同胞的你准备自己采购一些粮食支援灾区，现在假设你一共有资金n元，而市场有m种大米，每种大米都是袋装产品，其价格不等，并且只能整袋购买。请问：你用有限的资金最多能采购多少公斤粮食呢？

 

思路

裸多重背包, 本想练练倍增优化的, AC 后又没动力了

 

代码

#include 
     
      #include 
      
       #include 
       
        using namespace std;int weight[222];int bags  [222];int money [222];int dp       [222];int main() {    int t;    scanf("%d", &t);    for(int i = 0; i < t; i ++) {        memset(dp, 0, sizeof(dp));        int n, m;        scanf("%d%d", &n, &m);                for(int j = 0; j < m; j ++)            scanf("%d%d%d", money+j, weight+j, bags+j);        for(int j = 0; j < m; j ++) {            for(int k = n; k >= 0; k --) {                for(int s = 1; s <= bags[j]; s ++) {                    if(k < s*money[j]) break;                    dp[k] = max(dp[k], dp[k-s*money[j]]+s*weight[j]);                }            }        }        int res = 0;        for(int j = 0; j <= n; j ++)            res = max(res, dp[j]);        cout << res << endl;    }    return 0;}