C++关于max函数的问题

Question

#include<bits/stdc++.h>
#define ll long long
#define MAXN (int)1e3+10
using namespace std;

ll N, V;
struct node {
    ll w, v, s;
} a;

//int max(int a, int b) {
//    if (a > b) {
//        return a;
//    }
//    return b;
//}

struct node2 {
    ll w, v;
}b;
int main() {
    cin >> N >> V;
    vector<node> nodes;
    vector<node2> new_nodes;
    for (int i = 1; i <= N; i++) {
        cin >> a.w >> a.v >> a.s;
        if (a.s == 0) {
            a.s = V / a.v;
        }
        nodes.push_back(a);
    }
    //对每一项进行二进制拆分
    for (node i : nodes) {
        int n = i.s;
        int num = 1;
        while (num < n) {
            b.v = i.v * num;
            b.w = i.w * num;
            n -= num;
            num *= 2;
            new_nodes.push_back(b);
        }
        b.w = i.w * n;
        b.v = i.v * n;
        new_nodes.push_back(b);
    }

    for (node2 i : new_nodes) {
        cout << i.v << " " << i.w << endl;
    }

    //进行动态规划，使用多重背包
    int dp[2][70];
    memset(dp, 0, sizeof(dp));
    for (int i = 0; i < new_nodes.size(); i++) {
        for (int j = 0; j <= V; j++) {
            if (j - new_nodes[i].w < 0) {
                dp[i % 2][j] = dp[(i - 1) % 2][j];
            }
            else {
                dp[i % 2][j] = max(dp[(i - 1) % 2][j], dp[(i - 1) % 2][j - new_nodes[i].w]+new_nodes[i].v);
            }

        }
    }
}

为什么这里面的max函数用不了

Answer 1

引自免费微信小程序：皆我百晓生

从你提供的代码中可以看出，你试图在多重背包的动态规划部分使用max函数来确定状态转移的值。但在这个代码中，存在几个问题可能导致max函数无法正常工作。让我们一步步来解决这些问题。

首先，你应该包含 <algorithm> 头文件以使用 std::max 函数。因为 max 函数是在 <algorithm> 头文件中定义的。修改代码：

#include <algorithm> // 添加这一行以使用 max 函数

其次，你的动态规划部分的实现似乎有些问题。你试图使用二维数组 dp 来存储状态转移的值，但你没有正确地初始化这个数组。你需要确保 dp 数组在循环之前被正确初始化。另外，循环的顺序也需要调整，以确保状态转移的正确性。此外，你还需要确保每个节点的处理顺序是正确的。一个可能的动态规划实现如下：

// ... 其他代码保持不变 ...

vector<int> dp(V + 1, 0); // 初始化 dp 数组，值为 0
for (node2 i : new_nodes) { // 确保按正确的顺序处理节点
    for (int j = V; j >= i.w; j--) { // 确保当前背包容量足够放置该节点物品
        dp[j] = max(dp[j], dp[j - i.w] + i.v); // 更新状态转移方程
    }
}
cout << dp[V] << endl; // 输出最大价值

请注意，我在上述代码中使用了 vector<int> 来存储 dp 数组，因为动态规划中的状态数量是有限的（最多到 V）。这样做使得代码更简洁并且更有效。我还调整了循环的顺序和条件以确保状态转移的正确性。此外，我去掉了不必要的取模操作，因为它在这里没有实际用途。最后，我直接输出了 dp[V]，这是背包容量为 V 时的最大价值。希望这些修改能帮助你解决问题！