Unbounded Knapsack Problem

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.

basic Knapsack Problem


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.

So, no need to keep a track.

Here, we’ll use array dp{W+1], dp[i] is the maximum profit that can be achieved with the Knapsack capacity of i. W is total knapsack capacity, therefore our answer is dp[W].

dp[i] = maximum profit that can be achieved with a knapsack capacity of i

We go through all of the items accessible for each knapsack capacity between 1 and W in order to see whether they may be employed to increase profit.

Our equation will look like.

dp[i] = max(dp[i], dp[i-wt[j]] + val[j]) if wt[j] < i (item j is taken)

The code is the following:

for i = 0 to W:

for j = 0 to N:

if wt[j] < i :

dp[i] = max(dp[i], dp[i-wt[j]] + val[j])

Assume we are given four objects with weights of 1, 2, 5, and 3, and the earnings associated with them are 40, 30, 50, and 25 in that order. The knapsack's capacity is specified as 2.


Continuing with our method, our dp array is first initialised to 0. We start by iterating from 1 to 6. (capacity of knapsack).


Our wt array = [1,2,5,3]

Our val array = [40,30,50,20]

Initial dp array = [0,0,0]


At first iteration it will go like this(i=0)

j=0 : wt[j] <= i not satisfied. (wt[0] = 1, i = 0)

j=1 : wt[j] <= i not satisfied. (wt[1] = 2, i = 0)

j=2 : wt[j] <= i not satisfied. (wt[2] = 5, i = 0)

j=3 : wt[j] <= i not satisfied. (wt[3] = 3, i = 0) </br>

dp array after the First iteration = [0,0,0]


At second iteration it will go like this(i=0)

j=0 : wt[j] <= i is satisfied. (wt[0] = 1, i = 1)

Thus, dp[1] = max(dp[1],dp[1-1]+val[0]) = max(0,0+40)=40.


j=1 : wt[j] <= i not satisfied. (wt[1] = 2, i = 1)

j=2 : wt[j] <= i not satisfied. (wt[2] = 5, i = 1)

j=3 : wt[j] <= i not satisfied. (wt[3] = 3, i = 1)

dp array after Second iteration = [0,40,0]


At third iteration it will go like this(i=0)

j=0 : wt[j] <= i is satisfied. (wt[0] = 1, i = 1)

Thus, dp[1] = max(dp[1],dp[1-1]+val[0]) = max(0,0+40)=40.


j=1 : wt[j] <= i not satisfied. (wt[1] = 2, i = 1)

j=2 : wt[j] <= i not satisfied. (wt[2] = 5, i = 1)

j=3 : wt[j] <= i not satisfied. (wt[3] = 3, i = 1)

dp array after Second iteration = [0,40,0]


Now, as i = W (knapsack capacity), the iteration will stop. The profit(maximum) achieved is dp[2] = 80. Item 1 is used two times, as weight = 1 and profit = 40.

Complexities


Time complexity:


Space complexity:


Here, W = Knapsack Capacity, N = No. of items.

Now, after understanding the concept and loop now let’s see the final code.

Into the languages


C++


#include <bits/stdc++.h>

using namespace std;

long int UnboundedKnapsack(long int Capacity,long int n, long int weight[],long int val[]){

long int dp[Capacity+1];

for(int i=0;i < W+1;i++){

dp[i]=0;

}

for(int i=0;i < W+1;i++){

for(int j=0;j < n;j++){

if(weight[j] < i){

dp[i] = max(dp[i], dp[i-weight[j]] + val[j]);

}

}

}

return dp[Capacity];

}

int main(){

// The no. of items :

long int n = 4;

// Weights of all the items :

long int weight[4] = {5 , 10, 8, 15};

// Enter values of all the items :

long int val[4] = {40, 30, 50, 25};

// Enter the knapsack capacity :

long int Capacity = 120;

cout << "The maximum value you can achieve in Unbounded Knapsack is: " << UnboundedKnapsack(W,n,wt,val);

return 0;

}


Python


# Unbounded Knapsack Problem

def UnboundedKnapsack(Capacity,n,weight,val):

dp=[]

for i in range(Capacity+1):

dp.append(0)

for i in range(0,Capacity+1):

for j in range(0,n):

if weight[j] < i:

dp[i] = max(dp[i] , dp[i-weight[j]]+val[j])

return dp[Capacity]

''' No. of items '''

n = 4

''' Weights of all items '''

weight = [5,10,8,15]

''' Values of all items '''

val = [40,30,50,25]

''' Capacity of Knapsack '''

Capacity = 120

print("The maximum value possible is ",UnboundedKnapsack(Capacity,n,weight,val))


Java


import java.io.*;

import java.util.*;

import java.text.*;

import java.math.*;

import java.util.regex.*;

public class Solution {

public static int unboundedKnapsack(int Capacity,int n, int weight[],int val[]){

int[] dp = new int[Capacity+1];

for(int i=0;i < Capacity;i++){

dp[i]=0;

}

for(int i=0;i < Capacity;i++){

for(int j=0;j < n;j++){

if(weight[j] < i){

dp[i]=Math.max(dp[i],dp[i-weight[j]]+val[j]);

}

}

}

return dp[Capacity];

}

public static void main(String[] args) {

// No. of items

int n = 4;

// Values(Profits) of items

int val[] = {40,30,50,25};

// Weight of items

int weight[] = {5,10,8,15};

// Knapsack capacity

int Capacity = 120;

System.out.println("Maximum value that can be achieved is: "+unboundedKnapsack(Capacity,n,weight,val));

}

}

4.7 Star App Store Review!
Cpl.dev***uke
The Communities are great you rarely see anyone get in to an argument :)
king***ing
Love Love LOVE
Download

Select Collections