CODEWITHSUNDEEP
algorithmknapsack-problem
Another Student
Another Student

Reputation: 23

Printing items selected from Knapsack Unbounded algorithm?

I know how standard knapsack works, and i can afford to print the items selected in the 2D matrix, but from what i figured, unbounded knapsack is a 1D array. How do you print items selected by unbounded knapsack algorithm?

Upvotes: 1

Views: 2519

Answers (2)

Deepanshu Lulla
Deepanshu Lulla

Reputation: 65

Assuming dp[][] is a matrix that is populated correctly. We can backtrack to find selected weights


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

For details on how to generate this DP array from bottom up 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]

Upvotes: 0

Raman Kumar
Raman Kumar

Reputation: 21

Unbounded Knapsack can be solved using 2D matrix, which will make printing the included items easy. The items included in the knapsack can be backtracked from the matrix in the same way as in 0/1 Knapsack.

After the dp[][] matrix is populated, this will print the included items:

// 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];
        }
    }

Upvotes: 2

Related Questions