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

小明有n元钱，想要购买m种物品来最大化他的需求度。每种物品有两种类型：一种只能买一件（z=1），另一种可以买无限件（z=0）。每件物品都有价格x和需求度y。目标是用n元钱购买物品，使得总需求度最大化。

方法思路

这个问题可以通过动态规划来解决，具体来说，涉及到0-1背包和完全背包的结合。对于每种物品，根据其类型分别处理：

具体步骤如下：

解决代码

#include 
   
    #include 
    
     using namespace std;int main() {    int n, m;    cin >> n >> m;    int ans[n+1];    fill(ans, ans + n + 1, 0); // 初始化dp数组为0    for (int i = 1; i <= m; ++i) {        int x, y, z;        cin >> x >> y >> z;        if (z == 1) {            // 0-1背包：逆向填充            for (int j = n; j >= x; --j) {                if (j - x >= 0 && ans[j] < ans[j - x] + y) {                    ans[j] = max(ans[j], ans[j - x] + y);                }            }        } else {            // 完全背包：正向填充            for (int j = x; j <= n; ++j) {                if (ans[j] < ans[j - x] + y) {                    ans[j] = max(ans[j], ans[j - x] + y);                }            }        }    }    cout << ans[n] << endl;    return 0;}
    
   

代码解释

这个方法确保在有限的预算内，最大化需求度，适用于混合背包问题的典型场景。

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