背包0-1路径重建(需要采取的项目) [英] Knapsack 0-1 path reconstruction (which items to take)

问题描述

我知道如何使用动态编程方法解决背包0-1问题，但是在确定要取哪些物品而不影响O(N * C)(N个物品，C容量)的复杂性方面遇到了麻烦.

I know how to solve knapsack 0-1 problem with dynamic programming approach, but I am having troubles figuring out which items to take without compromising the complexity of O(N * C) (N items, C capacity).

有什么想法(我希望采用自下而上的方法)?

Any ideas (I would prefer a bottom-up approach)?

推荐答案

此处是对O(n)次重构路径的修改

Here is a modification to reconstruct path in O(n) times

int knapsack(int weight[], int profit[], int no_of_items, int capacity) {
    for (int var = 0; var <= capacity; ++var) {
        dp[0][var] = 0;
    }
    for (int var = 0; var <= no_of_items; ++var) {
        path[var] = false;
    }
    int using_item_i, without_using_item_i;
    for (int i = 1; i <= no_of_items; ++i) {
        for (int j = 1; j <= capacity; ++j) {
            without_using_item_i = dp[i - 1][j];
            using_item_i = 0;
            if ((weight[i]) <= j) {
                using_item_i = dp[i - 1][j - weight[i]] + profit[i];
            }

            if (using_item_i >= without_using_item_i) {
                taken[i][j] = true;
                dp[i][j] = using_item_i;
            } else {
                taken[i][j] = false;
                dp[i][j] = without_using_item_i;
            }
        }
    }
    //Reconstructing back the path
    int j = capacity;
    for (int i = no_of_items; i >= 0; --i) {
        if (taken[i][j]) {
            path[i] = true;
            cnt++;
        }
        j = j -  weight[i];
    }
    return dp[no_of_items][capacity];
}

这篇关于背包0-1路径重建(需要采取的项目)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！