Knapsack based famous problems, read KnapsackProperty.txt for more

1. 0-1 Knapsack.cpp

#include<bits/stdc++.h>
using namespace std;

void print2dVector(vector< vector<int> > v){
	int x = v.size();
	int y = v[0].size();
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
}

int knapsackRec(vector<int> wt,vector<int> val, int W, int N){
	if(N == 0 || W == 0){
		return 0;
	}
	//Weight of item greater than capacity of knapsack, we can't choose that item
	if(wt[N-1] > W){
		return knapsackRec(wt,val,W,N-1);
	}
	//We have to choose between 2 choices
	return max(val[N-1] + knapsackRec(wt,val,W-wt[N-1],N-1), knapsackRec(wt,val,W,N-1));//Icluding and not including the N-1th weight respectively
}

int knapsackMemoization(vector<int> wt,vector<int> val, int W, int N, vector<vector<int> > &result){
	if(N == 0 || W == 0){
		return 0;
	}
	if(result[N][W] != -1){
		return result[N][W];
	}
	int notConsidering;
	if(wt[N-1] > W){
		notConsidering = knapsackMemoization(wt,val,W,N-1,result);
		result[N][W] = notConsidering;
	}else{
		int considering = val[N-1] + knapsackMemoization(wt,val,W-wt[N-1],N-1,result);
		notConsidering = knapsackMemoization(wt,val,W,N-1,result);
		result[N][W] =  max(considering, notConsidering); 
	}
	return result[N][W];
}

int knapsackIterative(vector<int> wt,vector<int> val, int W, int N, vector<vector<int> > &result){
	for(int i=0;i<=N;i++){
		for(int j=0;j<=W;j++){
			if(i == 0 || j == 0){
				result[i][j] = 0;
			}else{
				if(wt[i-1] > j){
					result[i][j] = result[i-1][j];
				}else{
					result[i][j] = max(result[i-1][j], val[i-1] + result[i-1][j - wt[i-1]]);
				}
			}
		}
	}
	return result[N][W];
}

int main(){
	int N,W;
	cin >> N; //Number of items
	vector<int> wt(N),val(N);
	//Scanning weights of items
	for(int i=0;i<N;i++){
		cin >> wt[i];
	}
	//Scanning values of items
	for(int i=0;i<N;i++){
		cin >> val[i];
	}
	cin >> W; //Total capacity of Knapsack
	
	
	// Normal Recursive solution - without DP -> Time Complexity -> 2^n
	//cout << knapsackRec(wt,val,W,N) << endl;
	
	
	// For DP based approaches, we need to declare 2D array here
	// Need to declare the array to store the results for DP - Can be either global or passed into the function
	vector<vector<int> > res(N+1,vector<int> (W+1,-1));
	
	
	// Memoized recursive solution - with DP -> Time Complexity -> n^2 Space Complexity -> n^2
	//cout << knapsackMemoization(wt,val,W,N,res) << endl;
	
	
	// Tabulization based iterative solution - DP -> Time Complexity -> n^2 Space Complexity -> n^2
	cout << knapsackIterative(wt,val,W,N,res) << endl;
	return 0;
}

2. Subset sum.cpp

#include<bits/stdc++.h>
using namespace std;

bool subsetSum(vector<int> arr, int N, int sum){
	//2d boolean matrix which store T|F for [n][sum] if sum is possible if we include n elements
	bool result[N+1][sum+1];
	
	for(int i=0;i<=N;i++){
		for(int j=0;j<=sum;j++){
			if(i == 0 && j == 0){	// Empty array can give us sum = 0
				result[i][j] = true;
			}else if(i == 0){
				result[i][j] = false; // Empty array cannot give us sum > 0
			}else if(j == 0){	
				result[i][j] = true;	// Non-empty array can give us sum = 0 {Empty sub-array}
			}else{
				if(arr[i-1] > j){
					result[i][j] = result[i-1][j];
				}else{
					result[i][j] = result[i-1][j] || result[i-1][j- arr[i-1]];
				}
			}
		}
	}
	return result[N][sum];
}

int main(){
	int N,sum;
	cin >> N; //Number of elements
	vector<int> arr(N);
	//Scanning array of numbers
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	//Scanning sum to be found
	cin >> sum;
	subsetSum(arr,N,sum) ? cout << "T\n" : cout <<"F\n";	
	return 0;
}

3. Equal Sum Partition.cpp

#include<bits/stdc++.h>
using namespace std;

bool isEqualSumPartitionPossible(vector<int> arr, int N){
	//Check for sum of array [Even-Odd ruling out]
	int sum = 0;
	for(int i=0;i<N;i++){
		sum += arr[i];
	}
	if(sum % 2 != 0){
		return false;
	}
	sum = sum/2;
	//2d boolean matrix which store T|F for [n][sum] if sum is possible if we include n elements
	bool result[N+1][sum+1];
	
	for(int i=0;i<=N;i++){
		for(int j=0;j<=sum;j++){
			if(i == 0 && j == 0){	// Empty array can give us sum = 0
				result[i][j] = true;
			}else if(i == 0){
				result[i][j] = false; // Empty array cannot give us sum > 0
			}else if(j == 0){	
				result[i][j] = true;	// Non-empty array can give us sum = 0 {Empty sub-array}
			}else{
				if(arr[i-1] > j){
					result[i][j] = result[i-1][j];
				}else{
					result[i][j] = result[i-1][j] || result[i-1][j- arr[i-1]];
				}
			}
		}
	}
	return result[N][sum];
}

int main(){
	int N;
	cin >> N; //Number of elements
	vector<int> arr(N);
	//Scanning array of numbers
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	isEqualSumPartitionPossible(arr,N) ? cout << "T\n" : cout <<"F\n";	
	return 0;
}

4. Minimum Subset Difference.cpp

#include<bits/stdc++.h>
using namespace std;

int minSubsetSumDifference(vector<int> arr, int N, int sum){
	//2d boolean matrix which store T|F for [n][sum] if sum is possible if we include n elements
	bool result[N+1][sum/2+1];
	
	for(int i=0;i<=N;i++){
		for(int j=0;j<=sum/2;j++){
			if(i == 0 && j == 0){	// Empty array can give us sum = 0
				result[i][j] = true;
			}else if(i == 0){
				result[i][j] = false; // Empty array cannot give us sum > 0
			}else if(j == 0){	
				result[i][j] = true;	// Non-empty array can give us sum = 0 {Empty sub-array}
			}else{
				if(arr[i-1] > j){
					result[i][j] = result[i-1][j];
				}else{
					result[i][j] = result[i-1][j] || result[i-1][j- arr[i-1]];
				}
			}
		}
	}
	
	/*for(int i=0;i<=N;i++){
		for(int j=0;j<=sum/2;j++){
			result[i][j] ? cout << "T " : cout << "F ";
		}
		cout << endl;
	}*/
	
	int ans = INT_MAX;
	//cout << "ans: ";
	for(int i=0;i<=sum/2;i++){
		if(result[N][i]){
			ans = min(ans,sum - 2*i);
			//cout << ans << " ";
		}
	}
	//cout << endl;
	//cout << ans << endl;
	return ans;
}

int main(){
	int N,sum=0;
	cin >> N; //Number of elements
	vector<int> arr(N);
	//Scanning array of numbers
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	//Calaculating sum of given array
	for(int i=0;i<N;i++){
		sum += arr[i];
	}
	cout << minSubsetSumDifference(arr,N,sum) << endl;	
	return 0;
}

5. Target sum (LeetCode).cpp

#include<bits/stdc++.h>
using namespace std;

int numberOfSubsetWithSum(vector<int> arr, int N, int sum){
	//2d boolean matrix which store T|F for [n][sum] if sum is possible if we include n elements
	int result[N+1][sum+1];
	
	for(int i=0;i<=N;i++){
		for(int j=0;j<=sum;j++){
			if(i == 0 && j == 0){	// Empty array can give us sum = 0
				result[i][j] = 1;
			}else if(i == 0){
				result[i][j] = 0; // Empty array cannot give us sum > 0
			}else if(j == 0){	
				result[i][j] = 1;	// Non-empty array can give us sum = 0 {Empty sub-array}
			}else{
				if(arr[i-1] > j){
					result[i][j] = result[i-1][j]; //Exclude current element
				}else{
					result[i][j] = result[i-1][j] + result[i-1][j- arr[i-1]]; //Exclude & Include respectively
				}
			}
		}
	}
	return result[N][sum];
}

int main(){
	int N,sum;
	cin >> N; //Number of elements
	vector<int> arr(N);
	//Scanning array of numbers
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	//Scanning sum to be found
	cin >> sum;
	cout << numberOfSubsetWithSum(arr,N,sum) << endl;
	return 0;
}

6. Unbounded Knapsack (Rod cutting problem).cpp

#include<bits/stdc++.h>
using namespace std;

void print2dVector(vector< vector<int> > v){
	int x = v.size();
	int y = v[0].size();
	for(int i=0;i<x;i++){
		for(int j=0;j<y;j++){
			cout << v[i][j] << " ";
		}
		cout << endl;
	}
}

int unboundedKnapsackRec(vector<int> wt,vector<int> val, int W, int N){
	if(N == 0 || W == 0){
		return 0;
	}
	//Weight of item greater than capacity of knapsack, we can't choose that item
	if(wt[N-1] > W){
		return unboundedKnapsackRec(wt,val,W,N-1);
	}
	//We have to choose between 2 choices
	return max(val[N-1] + unboundedKnapsackRec(wt,val,W-wt[N-1],N), unboundedKnapsackRec(wt,val,W,N-1));
	//Icluding and not including the N-1th weight respectively
	//In case we are including, we may or may not include again 
	//so we will not divert from that item, elsewise, we will shift to
	//(N-1)th item
}

int unboundedKnapsackMemoization(vector<int> wt,vector<int> val, int W, int N, vector<vector<int> > &result){
	if(N == 0 || W == 0){
		return 0;
	}
	if(result[N][W] != -1){
		return result[N][W];
	}
	int notConsidering;
	if(wt[N-1] > W){
		notConsidering = unboundedKnapsackMemoization(wt,val,W,N-1,result);
		result[N][W] = notConsidering;
	}else{
		//In case we are including, we may or may not include again 
		//so we will not divert from that item, meaning we will remain at Nth item
		int considering = val[N-1] + unboundedKnapsackMemoization(wt,val,W-wt[N-1],N,result);
		notConsidering = unboundedKnapsackMemoization(wt,val,W,N-1,result);
		result[N][W] =  max(considering, notConsidering); 
	}
	return result[N][W];
}

int unboundedKnapsackIterative(vector<int> wt,vector<int> val, int W, int N, vector<vector<int> > &result){
	for(int i=0;i<=N;i++){
		for(int j=0;j<=W;j++){
			if(i == 0 || j == 0){
				result[i][j] = 0;
			}else{
				if(wt[i-1] > j){
					result[i][j] = result[i-1][j];
				}else{
					//In case we are including, we may or may not include again 
					//so we will not divert from that item, elsewise, we will shift to
					//(i-1)th item
					result[i][j] = max(result[i-1][j], val[i-1] + result[i][j - wt[i-1]]);
				}
			}
		}
	}
	return result[N][W];
}

int main(){
	int N,W;
	cin >> N; //Number of items
	vector<int> wt(N),val(N);
	//Scanning weights of items
	for(int i=0;i<N;i++){
		cin >> wt[i];
	}
	//Scanning values of items
	for(int i=0;i<N;i++){
		cin >> val[i];
	}
	cin >> W; //Total capacity of Knapsack
	
	
	// Normal Recursive solution - without DP -> Time Complexity -> 3^n
	//cout << unboundedKnapsackRec(wt,val,W,N) << endl;
	
	
	// For DP based approaches, we need to declare 2D array here
	// Need to declare the array to store the results for DP - Can be either global or passed into the function
	vector<vector<int> > res(N+1,vector<int> (W+1,-1));
	
	
	// Memoized recursive solution - with DP -> Time Complexity -> n^2 Space Complexity -> n^2
	//cout << unboundedKnapsackMemoization(wt,val,W,N,res) << endl;
	
	
	// Tabulization based iterative solution - DP -> Time Complexity -> n^2 Space Complexity -> n^2
	cout << unboundedKnapsackIterative(wt,val,W,N,res) << endl;
	return 0;
}

7. Knapsack Hackerrank.cpp

#include<bits/stdc++.h>
using namespace std;

int unboundedKnapsackIterative(vector<int> arr, int sum){
	int N = arr.size();
	vector<vector<bool> > subset(N+1,vector<bool> (sum+1));
	for(int i=0;i<=N;i++){
        for(int j=0;j<=sum;j++){
            if(i==0 && j==0){
                subset[i][j] = true;
            }else if(i == 0){
                subset[i][j] = false;
            }else if(j == 0){
                subset[i][j] = true;
            }else{
                if(arr[i-1] > j){
                    subset[i][j] = subset[i-1][j];
                }else{
                    subset[i][j] = subset[i-1][j] || subset[i][j - arr[i-1]];
                }
            }
        }
    }
    int ans;
    for(int i=sum;i>=0;i--){
        if(subset[N][i]){
            ans = i;
            break;
        }
    }
    return ans;
}

int main(){
	int tCases;
	cin >> tCases;
	while(tCases--){
		int N,sum;
		cin >> N >> sum;
		vector<int> arr(N);
		for(int i=0;i<N;i++){
			cin >> arr[i];
		}
		cout << unboundedKnapsackIterative(arr,sum) << endl;
	}
	return 0;
}

8. Coin Change - Maximum Ways.cpp

#include<bits/stdc++.h>
using namespace std;

int coinChangeMaxWays(int arr[],int N,int sum){
	int result[N+1][sum+1];
	for(int i=0;i<=N;i++){
		for(int j=0;j<=sum;j++){
			if(i == 0 && j == 0){
				result[i][j] = 1;
			}else if(i == 0){
				result[i][j] = 0;
			}else if(j == 0){
				result[i][j] = 1;
			}else{
				if(arr[i-1] > j){
					result[i][j] = result[i-1][j];
				}else{
					result[i][j] = result[i-1][j] + result[i][j - arr[i-1]];
				}
			}
		}
	}
	return result[N][sum];
}

int main(){
	int N;
	cin >> N;
	int arr[N];
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	int sum;
	cin >> sum;
	cout << coinChangeMaxWays(arr,N,sum);
	return 0;
}

9. Coin Change - Minimum coins.cpp

#include<bits/stdc++.h>
using namespace std;

int coinChangeMinCoins(int arr[],int N,int sum){
	int result[N+1][sum+1];
	
	for(int i=0;i<=sum;i++){
		result[0][i] = INT_MAX-1;
	}
	for(int i=1;i<=N;i++){
		result[i][0] = 0;
	}
	for(int i=1;i<=sum;i++){
		if(i % arr[0] == 0){
			result[1][i] = i/arr[0];
		}else{
			result[1][i] = INT_MAX - 1;
		}
	}
	
	for(int i=2;i<=N;i++){
		for(int j=1;j<=sum;j++){
			if(arr[i-1] > j){
				result[i][j] = result[i-1][j];
			}else{
				result[i][j] = min(result[i-1][j], 1 + result[i][j - arr[i-1]]);
			}
		}
	}
	
	for(int i=0;i<=N;i++){
		for(int j=0;j<=sum;j++){
			cout << result[i][j] << " ";
		}
		cout << endl;
	}
	
	if(result[N][sum] == INT_MAX-1) 
            return -1;
    else
        return result[N][sum];
}

int main(){
	int N;
	cin >> N;
	int arr[N];
	for(int i=0;i<N;i++){
		cin >> arr[i];
	}
	int sum;
	cin >> sum;
	cout << coinChangeMinCoins(arr,N,sum);
	return 0;
}

KnapsackProperty.txt

Knapsack Property

# There will be item array/s and a capacity(max/min/nearest): 
- In case of 0-1 knapsack itself, there are 2 arrays for each item,
  namely weight and value
- The capacity in 0-1 knapsack is the capacity of bag

# We'll have choice for each item, whether to choose or not based on some constraints

# Difference b/w 0-1 and ubounded knapsack is:
- 0-1 has limited quantity of an item
- unbounded has unlimited quantity of an item

=> Approaching the problem is simple:
- If you don't remeber the base knapsack problem(0-1 or unbounded),
  (+) Start with recursive solution :
   Step 1: Form base condition based on input/s (Think of smallest valid input)
   Step 2: Make a choice diagram (Based on various conditions to choose item or not).
		   Based on choice diagram, write the main logic breaking down the problem
		   into further sub-problems via recursion.
   Step 3: Analyze the output required 
   Step 4: Write code for basic knapsack
   Step 5: Match similarity with knapsack (0-1 or unbounded)
   Step 6: Figure the analogy and change the variales as per the requirement in 
		   current written code
  (+) If you have recursive code for a problem, convert it into memoized form : 
   Step 1: Make an array(let's name it dp) to store the result of sub problems 
		   and final answer
   Step 2: To decide the dimensions of array check number of variables changing
		   in recurive code with each smaller problem (considering 2 - for same page)
   Step 3: Check if dp[i][j] exists - if yes, return it, if no calculate using
		   recursive code as already written and store for (i,j)
  (+) If you want to write tabulized code
   Step 1: Be familiar with the choice diagram/recursive code
   Step 2: Decide dimensions of array as mentoned in memoization step 2
   Step 3: Initialize first row and column (except in some cases where extra row/col
		   initialization is required - Min number of coins - Variation of unbouned)
		   To know value from which the array should be initialized, check base
		   condition of recursion.
   Step 4: Write logic code from choice diagram/recursive logic
   Step 5: Return answer(directly dp[N][M] or manipulative form of dp[N][M])
   
* When only one item array is given, check if we require 2nd. 
 - If yes, we would be able to construct it from 1st.
 - If not, consider given array as weight array and neglect val array when comparing
   with Knapsack code
* Worst approach is Recursion based. In most cases,
  Memoization(Top down) = Tabulation(Bottom up) but there are 
  scenarios where memoization gives stack overflow
* In scenarios where only precious row is required we can 
  optimize space by taking only 2 rows.