A Definitive Guide to Knapsack Problem

Board Infinity -

Introduction

In the Knapsack Problem, we must select the best solution out of all feasible options. We are given a set of items with varying weights and values in this problem. We must identify the best solution using an optimized approach. Find the largest value subset of val[] such that the sum of weights of the subset is less than or equal to W, given an integer W that denotes knapsack capacity. You must either pick it in its entirety or not at all (0-1 property)

  • The 0-1 Knapsack Problem is defined in this article, along with the algorithm's simple logic.
  • We discover how to apply the top-down, bottom-up, and recursive methods to solve the 0-1 Knapsack Problem.
  • We analyze the time and space complexity of the problem

Implementation

Utilizing the Memoization Technique would be best for this problem since subproblems overlap. We extend the recursive approach to help with the issue of redundant calculations and resulting complexity.  Hands down the fastest solutions.

Steps:

Simply building a 2-D array that can store a specific state (n, w) if we encounter it for the first time will allow us to solve this issue.

If we encounter the same state (n, w) again, simply return the stored result in the table in constant time rather than computing it in exponential complexity.

Code:

#include <bits/stdc++.h>
using namespace std;
int knapSack(int maxW, int wt[], int val[], int n)
{
    // making and initializing dp array
    int dp[maxW + 1];
    memset(dp, 0, sizeof(dp));
    for (int x = 1; x < n + 1; x++) {
        for (int w = maxW; w >= 0; w--) {
            if (wt[x - 1] <= w)
                // finding the maximum value
                dp[w] = max(dp[w], dp[w - wt[x - 1]] + val[x - 1]);
        }
    }
    return dp[maxW]; // returning the maximum value of knapsack
}
int main()
{
    int val[] = { 60, 100, 120 };
    int wt[] = { 10, 20, 30 };
    int maxW = 50;
    int n = sizeof(val) / sizeof(val[0]);
    cout << knapSack(maxW, wt, val, n);
    return 0;
}


write your code here: Coding Playground

Output: 220

Algorithm Complexity

  • Time Complexity: O(N*W).
    We leverage overlapping subproblems so we need not calculate the same nodes again and again.
  • Auxiliary Space: O(N*W) + O(N).
    Recursion stack consists of 2D array data structure for storing intermediate states and O(N) auxiliary stack space.

Points to Remember

  • We must choose the best combination of items from all possible sets for the Knapsack Problem.
  • This is a valid combination if the combined weight of all the items is <= to the knapsack's maximum carrying capacity.
  • We can choose whether or not to keep a certain item in the Knapsack. There is no option to keep something partially inside the knapsack.
  • It is resolved using dynamic programming. The recursion approach's time complexity can be reduced to O(n*W). With top-down/bottom-up dynamic programming, O(nW) can be achieved.