Today we review the code for unit and fractional knapsack problems. In these problems, a thief is trying to fill his bag with as much value of items  with as little weight as possible.  The solution looks like this for the unit case:
recursive  solution
/ Input:
// Values (stored in array val)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)
int knapsack( int W, int[] wt, int[] val, int n)
{
if (n== 0 || W == 0)
    return 0;
if (wt[n-1] > W)
   return knapsack(W, wt, val, n-1);

return max(
                    val[n-1] + knapsack(W-wt[n-1], wt, val, n-1),
                    knapsack(W, wt, val, n -1)
                   );
}
In the fractional case, we have the following:
int fractional-knapsack( int W, int[] wt, int[] val, int n) // wt is sorted based on val[i]/w[i]
{
if (n== 0 || W == 0)
    return 0;

return max(
                    val[n-1] + fractional-knapsack(W-wj + wj -w, wt, val, n),
                    val[n-1] + fractional-knapsack(W-wj, wt, val, n -1),
                    fractional-knapsack(W, wt, val, n-1)
                   );
}
which we can further improve by leaving the dynamic programming approach and applying the top down greedy choice property
wt.sort() // based on val[i]/wt[i]
n = wt.Count()
int fractional-knapsack-greedy-recursive(int W, int[] wt, int[] val, int n)
{
if (n== 0 || W == 0)
    return 0;

// first the selection
if (wt[n-1] > W)
{
return val[n-1]/wt[n-1]*W;
}
else
{
    // then the recursion
    return val[n-1] +  fractional-knapsack-recursive(W-wt[n-1], wt, val, n -1);
}
}

Today we review longest common subsequence instead of longest increasing subsequence
The LCS is based on the optimal substructure as follows: X, Y are sequences and Z is the LCS
1. if xm = yn, then zk = xm = yn and Zk-1 is the LCS of Xm-1 and Yn-1
2. if xm <> yn, then zk <> xm implies that Z is an LCS of Xm-1 and Y.
3. if xm <> yn, then zk <> yn, implies that Z is an LCS of X and Yn-1

The length of the longest common subsequence c[i,j] is :
1. 0 if i = 0 or j = 0
2. c[i-1, j-1] + 1 if i,j > 0 and xi = yj
3. max(c[i,j-1], c[i-1, j]) if i, j  > 0 and xi != yj

LCS-Length(x, y)
m <- length(x)
n<-length(y)
for i = 1 to m
     c[i, 0] = 0
for j = 0 to n
     c[0,j] = 0
for i = 1 to m
      for j = 1 to n
            if xi == yi
               c[i,j] = c[i -1, j-1] + 1
               b[i,j] = up-left
            elseif c[i-1,j]  >= c[i, j-1]
               c[i,j] = c[i-1, j]
               b[i,j] = up
            else c[i,j] = c[i,j-1]
               b[i,j] = left
return c and b
Now the LCS can be printed with :
PRINT-LCS( b, X, i, j) // PRINT-LCS(b, X, length(X), length(Y))
if i = 0 or j = 0
     then return
if b[i,j] == up-left
     then PRINT-LCS (b, X, i-1, j-1)
             print xi
else if b[i,j] == up
           then PRINT-LCS(b,X,i-1,j)
else PRINT-LCS(b,X, i, j-1)

It can be hard to choose between longest common subsequence and longest increasing subsequence as a solution to a problem. For example, consider the box stacking problem where boxes of different l x b x h exist and we have to stack them up such that we can find the tallest tower

Previously in our earlier blog post we incorrectly referred to it as the longest common subsequence but it is in fact longest increasing subsequence for the formation of the tower.

The solution remains the same:
var msh = new List<int>();
for (int i = 1; i < = n; i++)
   for (int j = 0; j < i; j++)
    {
                if (w (j)*l(j) > w (i)*l (i) && max (msh [j] + 1) > msh (i)
                MSH (i) = msh[j] + 1;
    }
return msh.max();

while dynamic programming considers choices repeatedly, back tracking never considers an invalid option and reduces the number of options from the permutations.

Today we review another coding problem
Problem: There are a lot of cuboid boxes of arbitrary sizes.  Find the largest subset of cubes that can fit into each other.
Solution: This problem can be simplified if we think about cubes. Cubes can fit into each other based on their sorted edges.. This reminds us of a longest increasing subsequence (LIS) problem.
We recall the solution of the LIS problem as :
x can be a single-element increasing sequence or
x can be appended at the end of the longest increasing subsequence ending at some y provided that y precedes x and y < x
For example, 
Edges          11, 1, 10,  4, 3, 2, 8, 7, 12, 6, 9, 5
Length of     1   1    2   2  2  2  3  3   4   3  4, 3
subsequence
This we can now code as :
int getLIS(List<int> cubeedges)
{
var lis = new List<int>();
for (int i = 0; i < cubeedges.Count(); i++)
{
 for (int j = 0; j < i; j ++)
  {
      if (cubeedges[j] < cubeedges[i] && lis[j] + 1 > lis[i])
                     lis[i] = lis[j] + 1;
   }
}
return list.max();
}
The above is O(N^2). We can have  a O( N LogN ) solution also
Formally,
Let X[i] represent the sequence 2, 3, 1
Let M[j] store the index k of the smallest value X[k] so that there is an increasing subsequence of length j ending at X[k] on the range k <=i and j <=k <= i.  j represents the length of the increasing subsequence and k represents the index of termination.
and Let P[k] store the index predecessor of X[k]
The longest Increasing subsequence  at any given point is given by X [M [1]], X [M [2]], ... X [M [L]] and if there is an increasing subsequence at i then there is one at i-1 which is X [P [M[i]]] and between these two bounds we can do a logarithmic search for j <=k <= i
Therefore the steps are:
P = array of length N  - all initialized to zero
M = array of length N + 1 // pad on the left so that we can use zero based index.
L = 0
for i in range 0 to N-1:
      Binary search for the largest positive j <= L
      such that X[M[j]] < X[i]
      lo = 1
      hi = L
      Binary Search between lo and hi adjusts lo and hi
      After searching lo is 1 greater than the length of the longest prefix
      newL = lo
      The predecessor of X[i] is the last index of the subsequence of length newL-1
      P[i] = M[newL -1]
      M[newL] = i
      if newL > L:
          if we found a subsequence longer than L, update L
          L = newL

   // Reconstruct the longest increasing subsequence
T = array of length L
k = M[L]
for i in range L-1 to 0:
    T[i] = X[k]
     k = P[k]

return T
The only difference between cubes and cuboids is that we compare not one dimension but all three.

This means that all the edges in one must be smaller than the corresponding of the other 

Today we review a few more coding questions.

We can compare the coin counting puzzle with the classical knapsack problem. The knapsack problem is defined this way:
A thief robbing a store finds n items.
The ith item is worth vi dollars and weighs wi pounds, where vi and wi are
integers. The thief wants to take as valuable a load as possible, but he can carry at
most W pounds in his knapsack, for some integer W . Which items should he take?
(We call this the 0-1 knapsack problem because for each item, the thief must either
take it or leave it behind; he cannot take a fractional amount of an item or take an
item more than once.)

If the thief removes an item j from this load, the remaining load must be the most valuable load, weighing at most W-wj that the thief can take from the n-1 original items excluding j .
Therefore the knapsack problem can be written as follows:
case 1: with weight wj, find the maximum weights among n-1 weights to fill a bag that can hold W-wj
case 2: without weight wj, find the maximum weights among n-1 weights to fill a bag that can hold W

// Input:
// Values (stored in array v)
// Weights (stored in array w)
// Number of distinct items (n)
// Knapsack capacity (W)

for j from 0 to W do:
     m[0, j] := 0

for i from 1 to n do:
     for j from 0 to W do:
         if w[i-1] > j then:
             m[i, j] := m[i-1, j]
         else:
             m[i, j] := max(m[i-1, j], m[i-1, j-w[i-1]] + v[i-1])



The knapsack and the coin change are similar because we have to select the fewest high denomination
coins to reach a sum

we substitute the capacity W with the sum  to reach, the number of distinct items as n, the number of weights as denominations and the values as 1 each. We find the minimum instead of the maximum value as count of coins.

We can solve the previous problem by using combinations as shown below:
void CoinCount(ref List<int> coins, ref List<int>change, int amount, int start, int level)
{

for (int I = start; I < amount; I++)

{

for (int j = 1; i < coins.Count() && j <= amount/coins[I]; j++)

{

for (int k = 0; k < j; k++){
       change[level+k] = coins[i];
}

if (change.sum() == amount) Console.WriteLine("{0} with {1} elements", change.ToString(),
change.Count());

if (change.sum() < amount)

      CoinCount( ref coins, ref change, n, start+1, level+j);

for(int k = 0; k <j; k++){
      change[level+k] = 0;
}
}


The dynamic programming approach is as follows:

//
// returns the maximum sum that cannot be met by the given coins
//
public int CoinSumDP(List<int> coins, ref List<int> change, int amount, int start, int end) // start is for the type of coins and end is for the number of same coin and all coins appear in sorted duplicate manner and using start,end for contiguity start = 0; end = change.Count [start,end] range initialized to zero
{
//pseudo code
if (coins.Count() == 1) return Coins[0];
int sum = 0;
for (int i = 0; i < Coins.Count(); i++)
    var q = CoinSumDP(Coins.ChooseK(), ref change, amount, start, end) +
                  CoinSumDP(Coins[start].Repeat(end-start), ref change, amount, start, end)
    if q > sum
        sum = q
return Sum;
}

#leetcode codingexercise
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

Solution:
If the range of sums that can be generated using the first k numbers in coins is from 0 to r, and the next number has value x, then either:
• x <= r+1 and it is possible to generate any sum from 0 to r+x using the first k+1 numbers, or
• x > r + 1 and it is not possible to generate the sum r + 1, since x and all the following numbers have greater values.
We keep adding x=r+1 and counting such additions until r meets or exceeds n.

public int CoinChange(List<int> coins, int amount) {
    int lookup[amount+1] = {0};

    for (int i=0; i<coins.length; i++)
    {
        for (int n=1; n<=amount; n++)
        {
            if (n > coins[i])
            {
                int countWithNewCoin = lookup[n-coins[i]] + 1;
                if (countWithNewCoin < lookup[n] || lookup[n]==0)
                    lookup[n] = countWithNewCoin;
            }

        }
    }
    return lookup[amount];
}
Coins 1,3
amount 5
lookup               0 1 2 3 4 5
Coins[1]               1 2 3 4 5
Coins[2]                        2 3
courtesy : internet posts prismo skills

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Any combination of perfect square numbers with or without repetitions may yield the sum

We enumerate all and find the ones with the least number

Note the greedy approach does not work:  For example to get 12, we cannot say 9 + 1 + 1 + 1

void SquareSums(ref List<int> perfectsquares, ref List<int>candidate, int n, int start, int level)
{

for (int I = start; I < n; I++)

{

for (int j = 1; j <= n/perfectsquares[I]; j++)

{

for (int k = 0; k < j; k ++){
       candidate[level+k] = perfectsquares[i];
}

if (candidate.sum() == n) Console.WriteLine("{0} with {1} elements", candidate.ToString(),
candidate.Count());

if (candidate.sum() < n)

      SquareSums( ref perfectsquares, ref candidate, n, start+1, level+j);

for(int k = 0; k <j; k++){
      candidate[level+k] = 0;
}
}


}

}