Introduction
The knapsack problem is just like a bag is provided to you to keep some things to keep in it. The main idea is to increase the benefit while not increasing capacity.
This is based on Dynamic Programming. Unbound Knapsack is the extension or more advanced version of the basic Knapsack Problem. The major difference is there that we can use Unbounded Knapsack an infinite number of times ulike 0-1 Knapsack.
Now it’s time to solve a question and understand better.
Practice
N objects are given, each with a weight and value (benefit or profit). The goal is to stuff the backpack with enough products to make the most money possible without exceeding the rucksack's weight restriction. In the Unbounded form of the issue, we can choose one thing several times, but in the classical version, we can only select one item once.
S:-
Assume we have three objects, each of which is described by a tuple (weight, benefit). The following are the items:
(7, 12) ; (3, 2), (20, 41)
Now with a bag of capacity 58. The optimal filing is
Item 3 + 3 + 1 + 1 + 2
Now, the total benefit is (41+41+12+12+2) = 108 and total weight being 57 (< 59).
We will have covered all weight like:
Item 3 + 3 + 2 + 2 + 2 + 2 + 2 + 2
Now, the total weight becomes 59 but the benefit will be (41 * 2 + 2 * 6) = 94 (< 108)
So, in the previous combination, we have taken the optimal distribution.
Now it’s time to see the next approach, Brute force approach.
Brute Force Approach
If we're given a list of objects together with their weights and profits and asked to calculate the largest profit conceivable, the first thing that comes to mind is the brute-force method. Here, we'll attempt all conceivable combinations of things, keeping track of the earnings we make in each, and then computing the maximum of those profits as our response.
Let’s see the Pseudocode:
MaxProfit = 0
for i = 0 to 2^N:
bin = binary(i) // Convert number to binary
profit = 0
weight = 0
for j = 0 to bin.length():
if bin[j] is set: // bit j is set, we have to include that item.
if weight + wt[j] > W: // When weight of the combination exceeds Capacity, Break.
profit = 0
break
profit = profit + val[j]
weight = weight + wt[j]
MaxProfit = max(MaxProfit, profit) // Update max profit.
Choosing from all possible combinations in this manner would increase the order's temporal complexity.
Θ(2N)
As total nC0+nC1+....+nCn=2N are the possiblity of outcomes.This has increased computation time so this will be highly inefficient. This is the reason Dynamic Programming is required.
Dynamic Programming Approach
Dynamic Programming is the way to tackle this problem, Similar to classical Knapsack. The big difference here is that the 1-D array is to be used instead of 2-D array in the classical Knapsack. Well, this happens as we have an infinite supply of all the available elements.
Comments