首页 > 代码库 > hdu acm 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

hdu acm 2191 悼念512汶川大地震遇难同胞——珍惜现在，感恩生活

2024-07-15 07:29:04   226人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=2191

题目意思：有 资金 n 和 m 种类型的大米，对第 i 种类型的大米，价格、数量、袋数分别是： pi,  hi, ci，问最多能采购的大米的重量是多少。

      多重背包入门题~~~~~~

      在01 背包中两重循环之间多了一重循环  0 ~ bag[i] ：表示第 i 种物品的数量从0~bag[i] 枚举。

    

 1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 using namespace std; 5  6 const int maxn = 200 + 5; 7  8 int w[maxn], v[maxn], num[maxn]; 9 int dp[maxn];10 11 int main()12 {13     int T, money, kind;14     while (scanf("%d", &T) != EOF)15     {16         while (T--)17         {18             scanf("%d%d", &money, &kind);19             for (int i = 0; i < kind; i++)20                 scanf("%d%d%d", &v[i], &w[i], &num[i]);21             memset(dp, 0, sizeof(dp));22             for (int i = 0; i < kind; i++)23             {24                 for (int j = 0; j < num[i]; j++)    // 多了这个循环！！！25                 {26                     for (int k = money; k >= v[i]; k--)27                         dp[k] = max(dp[k], dp[k-v[i]] + w[i]);28                 }29             }30             printf("%d\n", dp[money]);31         }32     }33     return 0;34 }

 


联系
我们