打印从背包无界算法中选择的项目？

Question

我知道标准背包是如何工作的，并且我可以打印在2D矩阵中选择的项，但从我计算的结果来看，无界背包是一个一维数组。如何打印由无界背包算法选择的项目？

Answer 1

无界背包可以用二维矩阵来求解，这将使打印包含的项目变得容易。背包中包含的项目可以像0/1背包中一样从矩阵中回溯。

填充dp矩阵后，这将打印包含的项目：

// dp[val.length+1][sackWeight+1] is the matrix for caching.
// val[] is the array that stores the values of the objects
// and wt[] is the array that stores the weight of the corresponding objects.
int x = val.length, y = sackWeight;
    while (x > 0 && y > 0) {
        if (dp[x][y] == dp[x - 1][y])
            x--;
        else if (dp[x - 1][y] >= dp[x][y - wt[x - 1]] + val[x - 1]) 
            x--;
        else {
            System.out.println("including wt " + wt[x - 1] + " with value " + val[x - 1]);
            y -= wt[x - 1];
        }
    }

Answer 2

假设dp是一个正确填充的矩阵。我们可以回溯以找到选定的权重

def print_selected_items(dp, weights, capacity):
    idxes_list = []
    print("Selected weights are: ", end='')
    n = len(weights)
    i = n - 1
    while i >= 0 and capacity >= 0:
        if i > 0 and dp[i][capacity] != dp[i - 1][capacity]:
            # include this item
            idxes_list.append(i)
            capacity -= weights[i]
        elif i == 0 and capacity >= weights[i]:
            # include this item
            idxes_list.append(i)
            capacity -= weights[i]
        else:
            i -= 1
    weights = [weights[idx] for idx in idxes_list]
    print(weights)
    return weights

有关如何从自下而上DP生成此DP数组的详细信息。

def solve_knapsack_unbounded_bottomup(profits, weights, capacity):
    """
    :param profits:
    :param weights:
    :param capacity:
    :return:
    """
    n = len(profits)
    # base checks
    if capacity <= 0 or n == 0 or len(weights) != n:
        return 0
    dp = [[-1 for _ in range(capacity + 1)] for _ in range(n)]
    # populate the capacity=0 columns
    for i in range(n):
        dp[i][0] = 0
    # process all sub-arrays for all capacities
    for i in range(n):
        for c in range(1, capacity + 1):
            profit1, profit2 = 0, 0
            if weights[i] <= c:
                profit1 = profits[i] + dp[i][c - weights[i]]
            if i > 0:
                profit2 = dp[i - 1][c]
            dp[i][c] = max(profit1, profit2)
    # maximum profit will be in the bottom-right corner.
    print_selected_items(dp, weights, capacity)
    return dp[n - 1][capacity]