A thief is robbing a store and can carry a maximum weight of ‘W’ into his knapsack. There are 'N' items available in the store and the weight and value of each item is known to the thief. Considering the constraints of the maximum weight that a knapsack can carry, you have to find the maximum profit that a thief can generate by stealing items.
Note: The thief is not allowed to break the items.
For example, N = 4, W = 10 and the weights and values of items are weights = [6, 1, 5, 3] and values = [3, 6, 1, 4]. Then the best way to fill the knapsack is to choose items with weight 6, 1 and 3. The total value of knapsack = 3 + 6 + 4 = 13.
The first line contains a single integer 'T' representing the number of test cases.
The 'T' test cases are as follows:
The first line contains two integers 'N' and 'W', denoting the number of items and the maximum weight the thief can carry, respectively.
The second line contains 'N' space-separated integers, that denote the values of the weight of items.
The third line contains 'N' space-separated integers, that denote the values associated with the items.
The first and only line of output contains the maximum profit that a thief can generate, as described in the task.
The output of every test case is printed in a separate line.
1 <= T <= 10
1 <= N <= 10^3
1 <= W <= 10^3
1<= weights <=10^3
1 <= values <= 10^3
where 'T' is the number of test cases, ‘N’ is the number of items, "weights" is the weight of each item, "values" is the value of each item and ‘W’ is the maximum weight the thief can carry.
1
4 5
1 2 4 5
5 4 8 6
13
The most optimal way to fill the knapsack is to choose items with weight 4 and value 8, weight 1 and value 5.
The total value of the knapsack = 8 + 5 = 13.
1
5 100
20 24 36 40 42
12 35 41 25 32
101
Can you do this recursively? Try to solve the problem by solving its subproblems first.
This problem can be solved by solving its subproblems and then combining the solutions of the solved subproblems to solve the original problem. We will do this using recursion.
We will consider every subset of the given items and calculate the weight and value of each subset. We will consider only those subsets whose total weight is smaller than or equal to ‘W’. Finally, pick the subset with the maximum value.
The base case of the recursion would be when no items are left or the remaining capacity of the knapsack is 0.
How to generate subsets?
The thief has two options for each item, either pick it or leave it.
Thus, there are two cases for each item:
Note that we can only include an item in the set if and only if the weight of the item is less than or equal to the remaining weight of the knapsack.
Finally, return the maximum value of the items in the knapsack obtained by including or excluding the current item.
O(2 ^ N), where N is the number of items.
There are N items available and for each item, we can either include it or exclude it. In the worst case, we will be generating every possible subset of the given items. Thus, the final time complexity is O(2 ^ N).
O(N), where N is the number of items.
We are not using any external data structure. Only recursion stack space of O(N) size is used by the algorithm.
All tags
Sort by
Interview problems
KNAPSACK 0 1 TABULATION ACCEPTED ✅✅✅
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w) {
vector<vector<int>> dp(n, vector<int>(w + 1, 0));
for (int i = weights[0]; i <= w; i++) {
dp[0][i] = values[0];
}
for (int i = 1; i < n; i++) {
for (int wt = 0; wt <= w; wt++) {
int not_take = dp[i - 1][wt];
int take = 0;
if (weights[i] <= wt)
take = values[i] + dp[i - 1][wt - weights[i]];
dp[i][wt] = max(not_take, take);
}
}
return dp[n - 1][w];
}
Interview problems
0 1 KNAPSACK DP MEMOIZATION ACCEPTED ✅✅✅
#include <bits/stdc++.h>
int solve(int index, int weightLeft, vector<int> &weights, vector<int> &values,
vector<vector<int>> &dp) {
if (index == 0) {
if (weightLeft >= weights[0])
return values[0];
else
return 0;
}
if (dp[index][weightLeft] != -1)
return dp[index][weightLeft];
int not_pick = solve(index - 1, weightLeft, weights, values, dp);
int pick = 0;
if (weights[index] <= weightLeft)
pick = values[index] +
solve(index - 1, weightLeft - weights[index], weights, values, dp);
return dp[index][weightLeft] = max(pick, not_pick);
}
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w) {
vector<vector<int>> dp(n, vector<int>(w + 1, -1));
return solve(n - 1, w, weights, values, dp);
}
Interview problems
c++ soln with Space optimisation
#include<bits/stdc++.h>
int spaceOpt(vector<int> &value, vector<int> &weight, int n, int capacity){
vector<int>curr(capacity+1,0);
for(int w=weight[0];w<=capacity;w++){
if(weight[0]<=capacity){
curr[w]=value[0];
}
else
curr[w]=0;
}
for(int indx=1;indx<n;indx++){
for(int w=capacity;w>=0;w--){
int inclu=0;
if(weight[indx]<=w){
inclu=value[indx]+curr[w-weight[indx]];
}
int excl=0+curr[w];
curr[w]=max(inclu,excl);
}
}
return curr[capacity];
}
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w)
{
// Write your code here
return spaceOpt(values,weights,n,w);
}Interview problems
c++ sol using Tabulation (DP bottom up approach)
#include<bits/stdc++.h>
int solveTab(vector<int> &value, vector<int> &weight, int n, int capacity){
vector<vector<int>>dp(n,vector<int>(capacity+1,0));
for(int w=weight[0];w<=capacity;w++){
if(weight[0]<=capacity){
dp[0][w]=value[0];
}
else
dp[0][w]=0;
}
for(int indx=1;indx<n;indx++){
for(int w=0;w<=capacity;w++){
int inclu=0;
if(weight[indx]<=w){
inclu=value[indx]+dp[indx-1][w-weight[indx]];
}
int excl=0+dp[indx-1][w];
dp[indx][w]=max(inclu,excl);
}
}
return dp[n-1][capacity];
}
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w)
{
// Write your code here
return solveTab(values,weights,n,w);
}Interview problems
c++ code || 0 1 knapsack || upvote
int solve(vector<int>&values,vector<int>&weights,int n,int maxweight,vector<vector<int>>&dp)
{
if(n==0)
{
if(weights[0]<=maxweight)
{
return values[0];
}
else
{
return 0;
}
}
if(dp[n][maxweight]!=-1)
{
return dp[n][maxweight];
}
int include=0;
if(weights[n]<=maxweight)
{
include = values[n]+solve(values,weights,n-1,maxweight-weights[n],dp);
}
int exclude = solve(values,weights,n-1,maxweight,dp);
dp[n][maxweight] = max(include,exclude);
return dp[n][maxweight];
}
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w)
{
// Write your code here
vector<vector<int>>dp(n,vector<int>(w+1,-1));
return solve(values,weights,n-1,w,dp);
}
Interview problems
recursive,memoization and dp solution in c++
// Recursive
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w){
int length = values.size();
if(w==0 || n==0){
return 0;
}
if(w<weights[length-n]){
return maxProfit(values,weights,n-1,w);
}
int a = maxProfit(values,weights,n-1,w-weights[length-n])+values[length-n];
int b = maxProfit(values,weights,n-1,w);
return max(a,b);
}
// Memoization
int helper(vector<int> &values, vector<int> &weights, int n, int w,vector<vector<int>> &dp){
int length = values.size();
if(w==0 || n==0){
return 0;
}
if(dp[w][n] != -1){
return dp[w][n];
}
if(w<weights[length-n]){
return helper(values,weights,n-1,w,dp);
}
int a = helper(values,weights,n-1,w-weights[length-n],dp)+values[length-n];
int b = helper(values,weights,n-1,w,dp);
dp[w][n] = max(a,b);
return dp[w][n];
}
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w){
vector<vector<int>dp(w+1,vector<int>(n+1,-1));
return helper(values,weights,n,w,dp);
}
// dynamic programming:
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w){
// Write your code here
vector<vector<int>> dp(w+1,vector<int>(n+1,0));
for(int i = 1; i<=w; i++){
for(int j = 1; j<=n; j++){
if(i<weights[n-j]){
dp[i][j] = dp[i][j-1];
}else{
dp[i][j] = max(dp[i-weights[n-j]][j-1]+values[n-j], dp[i][j-1]);
}
}
}
return dp[w][n];
}
Interview problems
0 1 Knapsack || C++ Solution
#include <iostream>
#include <vector>
using namespace std;
int maxProfit(vector<int> &values, vector<int> &weights, int n, int w) {
vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= w; ++j) {
if (weights[i - 1] <= j) {
dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][w];
}
Interview problems
java all approches are done
import java.util.*;
public class Solution {
// private static int maxsum(int i,ArrayList<Integer> values, ArrayList<Integer> weights,int w,int[][] dp){
// if(i==0){
// if(weights.get(0)<=w) return values.get(0);
// else return 0;
// }
// if(dp[i][w] != -1) return dp[i][w];
// int notake = maxsum(i-1,values, weights, w,dp);
// int take = Integer.MIN_VALUE;
// if(weights.get(i)<=w) take = values.get(i)+maxsum(i-1, values, weights, w-weights.get(i),dp);
// return dp[i][w]=Math.max(notake,take);
// }
// public static int maxProfit(ArrayList<Integer> values, ArrayList<Integer> weights, int n, int w) {
// // Write your code here.
// int[][] dp = new int[n+1][w+1];
// for(int[] row : dp){
// Arrays.fill(row,-1);
// }
// return maxsum( n-1,values,weights, w,dp);
// }
// /* tabulatin*/
// public static int maxProfit(ArrayList<Integer> values, ArrayList<Integer> weights, int n, int w) {
// int[][] dp = new int[n+1][w+1];
// for(int i = weights.get(0); i <= w; i++) {
// dp[0][i] = values.get(0);
// }
// for(int i = 1; i < n; i++) {
// for(int wt = 1; wt <= w; wt++) {
// int notake = dp[i-1][wt];
// int take = (weights.get(i) <= wt) ? values.get(i) + dp[i-1][wt - weights.get(i)] : Integer.MIN_VALUE;
// dp[i][wt] = Math.max(notake, take);
// }
// }
// return dp[n-1][w];
// }
/* space optimized*/
public static int maxProfit(ArrayList<Integer> values, ArrayList<Integer> weights, int n, int w) {
int[] prev = new int[w + 1];
int[] curr = new int[w + 1];
for (int i = weights.get(0); i <= w; i++) {
prev[i] = values.get(0);
}
for (int i = 1; i < n; i++) {
for (int wt = 1; wt <= w; wt++) {
int notake = prev[wt];
int take = (weights.get(i) <= wt) ? values.get(i) + prev[wt - weights.get(i)] : Integer.MIN_VALUE;
curr[wt] = Math.max(notake, take);
}
// Copy elements from curr to prev
System.arraycopy(curr, 0, prev, 0, w + 1);
}
return prev[w];
}
}
Interview problems
Python easy solution
def f(idx,val,weights,n,w,dp):
if idx==0:
if weights[0]<=w:
return val[0]
else:
return 0
if dp[idx][w]!=-1:
return dp[idx][w]
nottake=0+f(idx-1,val,weights,n,w,dp)
take=float("-inf")
if weights[idx]<=w:
take=val[idx]+f(idx-1,val,weights,n,w-weights[idx],dp)
dp[idx][w]=max(take,nottake)
return dp[idx][w]
def maxProfit(val, weights, n, w):
dp=[[-1]*(w+1) for _ in range(len(val))]
return f(n-1,val,weights,n,w,dp)
Interview problems
Knapsack Problem
The Knapsack Problem is a classic optimization problem where the goal is to maximize the total value of items included in a knapsack, given their weights and values, without exceeding the knapsack's capacity. In this post, we'll explore three different approaches to solve this problem: the basic recursive approach, the memoization approach to optimize the recursive solution, and the tabulation approach for a bottom-up dynamic programming solution.
Recursive Approach: We'll start by discussing the basic recursive approach to solving the Knapsack Problem. This approach involves breaking down the problem into smaller subproblems and solving them recursively. However, this approach can be inefficient, leading to redundant calculations and exponential time complexity, especially for larger inputs
int knapRecursive(vector<int> &values, vector<int> &weights, int n, int w) {
if (n == 0 || w == 0) {
return 0;
}
if (weights[n - 1] > w) {
return knapRecursive(values, weights, n - 1, w);
}
return max(values[n - 1] + knapRecursive(values, weights, n - 1, w - weights[n - 1]),
knapRecursive(values, weights, n - 1, w));
}Memoization Approach: The memoization approach stores results in a memoization table, avoiding redundant calculations and significantly improving time complexity.
int knapTabulate(vector<int> &values, vector<int> &weights, int n, int w) {
vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][w];
}Tabulation Approach : The tabulation approach builds the solution iteratively using a table, avoiding recursion altogether and providing an efficient solution.
int knapTabulate(vector<int> &values, vector<int> &weights, int n, int w) {
vector<vector<int>> dp(n + 1, vector<int>(w + 1, 0));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= w; j++) {
if (weights[i - 1] <= j) {
dp[i][j] = max(values[i - 1] + dp[i - 1][j - weights[i - 1]], dp[i - 1][j]);
} else {
dp[i][j] = dp[i - 1][j];
}
}
}
return dp[n][w];
}hope you guys got this article useful..
