Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

关于完全背包理论中遍历顺序的问题 #2441

Open
lusr3 opened this issue Feb 15, 2024 · 0 comments
Open

关于完全背包理论中遍历顺序的问题 #2441

lusr3 opened this issue Feb 15, 2024 · 0 comments

Comments

@lusr3
Copy link

lusr3 commented Feb 15, 2024

在完全背包滚动数组的实现中,提到两个遍历顺序都是可以的,但是对于先背包容量再物品的遍历顺序而言,计算过程中的结果可能是错误的,但是最终得到的结果是正确的,不太理解为什么最终可以是正确的。

以以下数据为例:

  重量 价值
物品0 1 15
物品1 2 40
物品2 4 100

使用代码随想录中的测试代码,并输出中间结果:

// 先遍历背包,再遍历物品
void test_CompletePack() {
    vector<int> weight = {1, 2, 4};
    vector<int> value = {15, 40, 100};
    int bagWeight = 6;

    vector<int> dp(bagWeight + 1, 0);

    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
        for(int i = 0; i < weight.size(); i++) { // 遍历物品
            if (j - weight[i] >= 0) dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            printf("(%d, %d) %d ", i, j, dp[j]);
        }
        cout << endl;
    }
    // cout << dp[bagWeight] << endl;
}
int main() {
    test_CompletePack();
}

得到输出:
image

以其中 (0, 3) 处的结果为例,背包容量为 3 且只用第一个物品的时候,结果应该是 45,与输出的 55 不符;而最终结果如 (2, 6),即背包容量为 6 且用所有物品时,最大的价值确实是 140

请问该怎么理解其中的遍历顺序比较好?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant