To identify whether it is a knapsack problem or not we would be given choice either to add or to ignore numbers.
Knapsack problems are of three type
 Fractional Knapsack
 0/1 Knapsack
 Unbounded Knapsack
Ways of Solving Knapsack problems
Problem : We are given 2 arrays of weight and value & we have to find max profit (Burgler and the max weight that he could pick)
Knapsack Recursive
Solution
/**
* vArr is value array
* wArr is weight array
* W is weight available
* arrSize is array size
*
*/
public int getMaxProfit(int[] vArr, int[] wArr, int W, int arrSize) {
// base condition
if (arrSize == 0  W == 0) {
return 0;
}
int currItemWeight = wArr[arrSize  1];
int currIteamProfit = vArr[arrSize  1];
if (currItemWeight > W) {
return getMaxProfit(vArr, wArr, W, arrSize  1);
}
// Two choices either to include this weight or to exclude this weight
// Include this weight
int max1 = currIteamProfit + getMaxProfit(vArr, wArr, W  currItemWeight, arrSize  1);
// Exclude this weight and leave it to the other elements
int max2 = getMaxProfit(vArr, wArr, W, arrSize  1);
// return max weight
return max1 > max2 ? max1 : max2;
}
Knapsack Memoization
You can also use memoization technique. On analysis we can see only last two variables are changing. Thefore create an array of dd[numberOfValues + 1][W + 1]
and initialize all cells to 1. So before calling the recursive function check if value exists in array
Knapsack Topdown
Lets say vArr
= {3,4,2,5,1} and wArr
= {1, 2, 2, 4, 2} and max weight is 8 (ie. W
= 8). To represent it in table/matrix format 
 Number of rows = N + 1; where N is size of array
 Number of columns = W + 1;
 Since for max weight 0 (ie. W = 0), max value/profit is also 0. Therefore initialize all first column values as 0.
 Since no element is present in first row therefore for any weight profit is 0. Hence initialize all column values in first row as 0.
W = 0  W = 1  W = 2  W = 3  W = 4  W = 5  W = 6  W = 7  W = 8  W = 9  

v = 0, w = 0  0  0  0  0  0  0  0  0  0  0 
v = 3, w = 1  0  
v = 4, w = 2  0  
v = 2, w = 2  0  
v = 5, w = 4  0  
v = 1, w = 2  0 
A single cell represent the max value for a particular weight. Lets say the array is called dd[N + 1][W + 1]
the recursive code can be rewritten as
int[][] dd = new int[N + 1][W + 1];
for (int j = 0; j <= W; i++) {
dd[0][j] = 0;
}
for (int i = 0; i <= N; i++) {
dd[i][0] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {
int currItemWeight = wArr[i  1];
int currItemValue = vArr[i  1];
// If current item weight is greater then get max value of its predecessor numbers, here j represents the weight
if (currItemWeigth > j) {
dd[i][j] = dd[i  1][j];
continue;
}
int max1 = dd[i  1][j];
int max2 = currItemValue + dd[i  1][j  currItemWeight];
dd[i][j] = max1 > max2 ? max1 : max2;
}
}
return dd[N][W];
Type of Knapsack Problems

Subset Sum

Equal Sum Partition

Count of Subset Sum

Minimum Subset Sum Diff

Target Sum

Number of Subet with given difference
Subset Sum Problem
Given a set of nonnegative integers, and a value sum, determine if there is any subset whose sum equal to given number (sum).
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 9
Output: True
There is a subset (4, 5) with sum 9.
Input: set[] = {3, 34, 4, 12, 5, 2}, sum = 30
Output: False
There is no subset that add up to 30.
In this scenario first column cells are true and the first row values are false. This is because at W = 0 there is a subset always present whose weight is equal to 0 that is empty subset.
W = 0  W = 1  W = 2  W = 3  W = 4  W = 5  W = 6  W = 7  W = 8  W = 9  

0  T  F  F  F  F  F  F  F  F  F 
3  T  
34  T  
4  T  
12  T  
5  T  
2  T 
Solution
int[] set = new int[]{3, 34, 4, 12, 5, 2};
boolean[][] dd = new boolean[N + 1][W + 1];
for (int j = 0; j <= W; i++) {
dd[0][j] = 0;
}
for (int i = 0; i <= N; i++) {
dd[i][0] = 0;
}
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= W; j++) {]
int currItemValue = set[i  1];
// If current item weight is greater then get max value of it predecessor numbers, here j represents whether set contains subset of particular weight or not
if (currItemWeight > j) {
dd[i][j] = dd[i  1][j];
continue;
}
boolean max1 = dd[i  1][j];
boolean max2 = dd[i  1][j  currItemWeight];
dd[i][j] = max1  max2;
}
}
return dd[N][W];
Equal Sum Partition
Given a nonempty array nums
containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
Lets say total
is the sum of all the elements of array. If total
is odd number then it is not possible to divide the array into two equal parts.
This problem is much like Subset Sum problem. If we have to divide the array into two equal parts (based on their sum) then it can be safe to say that the sum of one partition is equal to total / 2
. Now we just have to find out a subset in the array whose sum is equal to total / 2
. So we can solve this problem using Subset Sum problem.
**Practice : ** https://leetcode.com/problems/partitionequalsubsetsum/
Memoization
class Solution {
public boolean canPartition(int[] nums) {
int total = IntStream.of(nums).sum();
if (total % 2 > 0) {
return false;
}
Boolean[][] memo = new Boolean[nums.length][total + 1];
return isSumAvailable(nums, total / 2, 0, memo);
}
private boolean isSumAvailable(int[] nums, int total, int indexToStart, Boolean[][] memo) {
if (total == 0) {
return true;
}
if (indexToStart == nums.length) {
return false;
}
if (memo[indexToStart][total] != null) {
return memo[indexToStart][total];
}
if (nums[indexToStart] > total) {
memo[indexToStart][total] = isSumAvailable(nums, total, indexToStart + 1, memo);
} else {
memo[indexToStart][total] = (isSumAvailable(nums, total, indexToStart + 1, memo)  isSumAvailable(nums, total  nums[indexToStart], indexToStart + 1, memo));
}
return memo[indexToStart][total];
}
}
Top Down DP
class Solution {
public boolean canPartition(int[] nums) {
int total = 0;
for (int num: nums) {
total += num;
}
if (total % 2 == 1) {
return false;
}
int W = total / 2;
int N = nums.length;
boolean[][] dd = new boolean[N + 1][W + 1];
for (int j = 1; j <= W; j++) {
dd[0][j] = false;
}
for (int i = 0; i <= N; i++) {
dd[i][0] = true;
}
for (int i = 1; i <= N; i++) {
int currNum = nums[i  1];
for (int j = 1; j <= W; j++) {
if (currNum > j) {
// If the current item is greater than j, then it will be dependent on its predecessor items to satisfy the condition
dd[i][j] = dd[i  1][j];
} else {
// If the current item i
dd[i][j] = dd[i  1][j]  dd[i  1][j  currNum];
}
}
}
return dd[N][W];
}
}
Count of Subset Sum
In the Subset Sum problem we just had to find that whether there is any subset present in the array whose sum is equal to a particular number. In this problem (Count of Subset Sum) we have to find the total number of subsets whose sum is equal to the given number.
Eg. {2, 3, 5, 6, 8, 10}
. Lets say we have to find total number of subsets whose sum is 10. So there are 3 subsets whose sum is 10  {2, 3, 5}
, {2, 8}
, {10}
.
In the previous problem we were using or operator. In the problem we will be using sum (+) operator.
W = 0  W = 1  W = 2  W = 3  W = 4  W = 5  W = 6  W = 7  W = 8  W = 9  W = 10  

0  1  0  0  0  0  0  0  0  0  0  0 
2  1  0  1  0  0  0  0  0  0  0  0 
3  1  0  1  1  0  1  0  0  0  0  0 
5  1  0  1  1  0  2  0  1  1  0  1 
6  1  0  1  1  0  2  1  1  2  1  1 
8  1  0  1  1  0  2  1  1  3  1  2 
10  1  0  1  1  0  2  1  1  3  1  3 
public int subarraySum(int[] nums, int target) {
if (nums == null  nums.length == 0  target == 0) {
return 0;
}
int[][] dd = new int[nums.length + 1][target + 1];
for (int i = 0; i <= nums.length; i++) {
dd[i][0] = 1;
}
for (int j = 1; j <= target; j++) {
dd[0][j] = 0;
}
for (int i = 1; i <= nums.length; i++) {
for (int j = 1; j <= target; j++) {
if (nums[i  1] > j) {
dd[i][j] = dd[i  1][j];
} else {
dd[i][j] = dd[i  1][j] + dd[i  1][j  nums[i  1]];
}
}
}
return dd[nums.length][target];
}
Minimum Subset Sum Difference
In this problem there is an array given and we have to partition the array into two subsets such that the difference between them is minimum.
The smallest subset value is less than or equal to TotalSumOfArray / 2. Now just use Subset Sum Problem with dd[arraySize + 1][TotalSumOfArray / 2]
and in the last row from j = TotalSumOfArray / 2 to j = 1 check first true. Then the minimum difference is TotalSumOfArray  2 * (last element having true)
Count the number of subset with a given difference
This is the combination of Count of Subset sum and Minimum subset sum difference problem.
Practice: https://leetcode.com/problems/targetsum/
Total  S1 = S2
S1  S2 = Diff
Total  S2 = S2 + Diff
S2 = (Total  Diff) / 2
class Solution {
public int findTargetSumWays(int[] nums, int target) {
if (nums == null  nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0] == target ? 1 : 0;
}
int total = 0;
for (int num : nums) {
total += num;
}
target = (total  target) / 2;
int[][] dd = new int[nums.length + 1][target + 1];
for (int i = 0; i <= nums.length; i++) {
dd[i][0] = 1;
}
for (int j = 1; j <= target; j++) {
dd[0][j] = 0;
}
for (int i = 1; i <= nums.length; i++) {
for (int j = 1; j <= target; j++) {
if (nums[i  1] > j) {
dd[i][j] = dd[i  1][j];
} else {
dd[i][j] = dd[i  1][j] + dd[i  1][j  nums[i  1]];
}
}
}
return dd[nums.length][target];
}
}
Target sum
We have to assign + and  signs in front of elements and after adding the numbers, find number of combinations such that it is equal to the target sum.
Practice: https://leetcode.com/problems/targetsum/