CODEWITHSUNDEEP
algorithm
user1781626
user1781626

Reputation:

Retrieving the items from Knapsack [one dimensional array implementation]

This algorithm works fine Are these 2 knapsack algorithms the same? (Do they always output the same thing)

How do we retrieve the items that were selected in the process?

This is the algorithm from the previous post 

for (int j = 0; j < N; j++) {
    if (C-w[j] < 0) continue;
    for (int i = C-w[j]; i >= 0; --i) { //loop backwards to prevent double counting
        dp[i + w[j]] = max(dp[i + w[j]], dp[i] + v[j]); //looping fwd is for the unbounded problem
    }
}
printf( "max value without double counting (loop backwards) %d\n", dp[C]);

This is an example:

For C = 9 and N = 3

Values and Weights: 
5 4
6 5
3 2

The Knapsack array is the following: 

0 0 3 3 5 6 8 9 9 11

Which gives the optimal value = 11 by choosing item 1 and item 2

How to retrieve the selected items? or How to know which items did we select? [Item 1 and Item 2]

Adding another example:

weight: 16 19 23 28
value: 2 3 4 5
C = 7

Iteration 1

0 16 16 16 16 16 16

Iteration 2

0 16 19 19 35 35 35

Iteration 3

0 16 19 23 35 39 42

Iteration 4

0 16 19 28 35 39 44

The optimal value = 44 with items 1 and 4

Upvotes: 3

Views: 739

Answers (1)

blubb
blubb

Reputation: 9900

Simply replace your max call by a check whether the just found solution is better than any previously seen. If so, store it away for later reference.

Upvotes: 2

Related Questions