Dynamic Programming: Longest increasing subsequence

Given a unordered array of numbers, remove the fewest number of numbers to produce the longest ordered sequence. Print count of fewest numbers to be removed, and the remaining sequence. For example, if input is 1 2 3 4 5 6 7 8 9 10, no (zero) numbers are removed, and input is the longest sequence. If input is, 1 2 3 8 10 5 6 7 12 9 4 0, then fewest number of elements to be removed is 5 is the fewest number to be removed, and the longest sequence is 1 2 3 5 6 7 12.



Recurrence.
For 1 <= i <= n,
A(i) = 1 + max{A(j) | 1 <= j < i and aj < ai}.
(We assume max(NULL) == 0.)


Time complexity: O(n2). 


Code input/output:
int [] A = {7, 3, 8, 4, 6};

LIS ends at: 4
MaxLength of LIS:3
Printing DP array: 
1 1 2 2 3 
Printing Previous Array:
-1 -1 1 1 3 
Printing LongestIncreasingSubsequence:
3 4 6 
Fewest numbers to be removed to produce the Longest ordered subsequence:2


int [] B = {0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15};
LIS ends at: 15
MaxLength of LIS:6
Printing DP array: 
1 2 2 3 2 3 3 4 2 4 3 5 3 5 4 6 
Printing Previous Array:
-1 0 0 2 0 4 4 6 0 6 8 9 8 9 12 13 
Printing LongestIncreasingSubsequence:
0 2 6 9 11 15 
Fewest numbers to be removed to produce the Longest ordered subsequence:10

Min depth of a binary tree.

Given a binary tree, compute min depth of a leaf node.


Hint:
1. BFS
2. Recursive implementation
Which is better in time complexity?


BFS has the better complexity.
Recursive implementation has to see all the paths in the tree, the number of paths from root would be 2^d where d is the max depth of the tree.
BFS has to see only 2^d where d is the min depth of the tree.


Code input/output:
Tree values (BST):
int [] A = {12, 9, 15, 4, 10, 13, 20, 14, 25, 30};

Min Depth Recursive: 2
Min Depth BFS: 2
Max Depth: 4

Regular Expression Matching.

 Input a string and a pattern having . and * Output: whether the string fully matches the pattern
. match any char, * means matching 0 or more times.
Example:
input "a", "." => match
input "abc", ".*" => match
input "abcd", "a.*d" => match


Code input/output:

Pattern: a.b*d
Text: acbmaxd
Is Exact Match:true


Pattern: .*
Text: acbmaxd
Is Exact Match:true


Pattern: c.*
Text: acbmaxd
Is Exact Match:false


Pattern: a*c.*x*
Text: acbmaxd
Is Exact Match:true


Pattern: a.*d
Text: acbmaxd
Is Exact Match:true


Pattern: .
Text: a
Is Exact Match:true

Evaluate Mathematical expressions.

Write a program to evaluate a simple mathematical expression like 4 + 2*a/b - 3 = ((4+(2*(7/2)))-3)


Approach:
Convert the give expression to reverse polish notation.

Expression: ((4+(2*(7/2)))-3)

Reverse polish notation: 4272/*+3-

Now traverse the reverse polish notation from left to right using stack.

When we see a operator while traversing from left to right we pop 2 operand, apply the operator and then push to result onto the stack.

step1: 4 2 7 2 / * + 3 -

first operator seen while traversing left to right is "/". the pop the operands "7" and "2" and apply the operator, result would be "3.5"

step2: 4 2 3.5 * + 3 -

second operator seen is "*", operands are "2" and "3.5", result is "7" - push this to stack.

step3: 4 7 + 3 -

third operator is "+" and operands are "4" and "7", result = 11, push this to stack.

step4: 11 3 -

fourth operator is "-" and operands are "11" and "3", result = 8, push this to stack.

setp5: 8

Now there are no more operators and we are done. 

Final ans is: 8.

Code input/output:

Expression: (2+(3*4))
Reverse polish notation: 234*+
Result:14.0


Expression: ((4+(2*(7/2)))-3)
Reverse polish notation: 4272/*+3-
Result:8.0

Function to remove duplicate from a String.

Code a function  that removes duplicate characters from a string.


Code input/output:

String: sstuuddents
After removing Duplicate chars: studen
String: mississippi
After removing Duplicate chars: misp

Binary Tree to Doubly Linked List.

Write code to convert a binary tree to doubly link list in place.


Code input/output:


Inserting following values in BST: 
98 84 92 58 57 20 34 
Printing BST inorder: 
20 34 57 58 84 92 98 
Printing the doubly linked list: 
20 <-> 34 <-> 57 <-> 58 <-> 84 <-> 92 <-> 98 <->  points to head 

Iterator for Binary Tree.

Implement an iterator for a Binary Tree.

Palindrome Counting and longest palindrome.

Count the number of palindromes and the longest palindrome in a give string.


Approach:
For each position of String S[i], calculate the number of odd length palindromes.
if S[i] == S[i+1] then calculate the number of even length palindromes.
while calculating odd and even length palindromes, keep track of the longest palindrome.


Time complexity: O(n^2).


Code input/output:

Input String: abacaba
Total palindromes: 5
Longes palindrome: abacaba
Palindromes are: 
aba aca bacab abacaba aba 


Input String: mamracecardudeabuttubathisist
Total palindromes: 11
Longes palindrome: abuttuba
Palindromes are: 
mam cec aceca racecar dud tt uttu buttub abuttuba isi sis 


Input String: mississippi
Total palindromes: 9
Longes palindrome: ississi
Palindromes are: 
ss issi sis ssiss ississi ss issi pp ippi 

Assign Phone numbers to people.

Suppose you are working for a phone company and you run the division that gives out phone numbers. Phone numbers are assigned in one of two ways:
a. bool GiveMeThisNumber(Person p, int number) Assigns the person a specific number that they requested, returning true if the number is available.
b. int GiveMeAnyNumber(Person p) Assigns the person any arbitrary number that is currently unassigned.
How would you design the algorithm for those methods? You can use any data structure you would like to hold the phone numbers.
Implement GiveMeThisNumber and GiveMeAnyNumber.

MRU cache.

Imagine you have data being pulled very frequently from a large database. How would you design a MRU (most recently used) cache?
Implement getValue(int id) for the MRU cache.


Approach:
Most Recently Used (MRU): discards, in contrast to LRU, the most recently used items first.
For random access patterns and repeated scans over large datasets (sometimes known as cyclic access patterns) MRU cache algorithms have more hits than LRU due to their tendency to retain older data.[4] MRU algorithms are most useful in situations where the older an item is, the more likely it is to be accessed.


MRU Cache:
1. For every Data Value we will have an attribute timestamp associated with it.
2. As Cache is a hashtable, we will store the values in a double linked list, on access of a Key Ki, its value Vi's attribute timestamp would change and we would put that node in the front of doubly linked list. ie it would become head.
3. Now if our predecided capacity is reached we would evict the head node of the linked list - since thats our MRU node.


Once we have the datastructure (like LinkedHashMap in java) ready then getValue(int id) is simply return of linkedHashMap.get(id);

Merge N Sorted Lists/Arrays.

Design and implement an algorithm to merge N sorted arrays.


Approach:
1. Take the head of all the N sorted arrays in a min-heap.
2. Get the min element from the min-heap and output/store it.
3. now pull out another element from the array to which the min-element in 2. belonged and add it to the heap and heapify it.
4. now repeat 2. & 3. till all the elements in N sorted arrays are exhausted.




Number of arrays: 7
48 52 202 459 589 647 700 794 
72 227 257 513 545 
151 327 361 691 821 
29 30 363 753 938 
120 178 314 364 409 662 695 
181 240 378 472 556 584 756 760 871 
87 111 242 275 368 376 815 944 966 
Final merged lists data: 
29 30 48 52 72 87 111 120 151 178 181 202 227 240 242 257 275 314 327 361 363 364 368 376 378 409 459 472 513 545 556 584 589 647 662 691 695 700 753 756 760 794 815 821 871 938 944 966 

Min and Max heap in Java

Code input/output:

Printing min heap data: 

12 13 14 15 17 19 20 44 45 52 56 58 74 84 

Printing max heap data

84 74 58 56 52 45 44 20 19 17 15 14 13 12 

Detect loop in a singly linked list.

Write code to detect a loop in a linked list.


Approach:
Keep 2 pointers at the head, say front and back.
Now move the front twice the speed as the back, if before back completing the one loop, the front pointer reaches back or overtakes it then there is loop in the singly link list.

Three integers sum in an array.

If you had to find all sets of three integers that summed up to a given value? How would you do this?


Code input/output:
int [] A = {5, 9, 2, 11, 3, 8, 15, 7, 4, 12, 1, 6};


Sorted Array A:


1 2 3 4 5 6 7 8 9 11 12 15 
triplets that sum to 12:
1:4:7
1:2:9
2:3:7
1:3:8
3:4:5
1:5:6
2:4:6

Pairs of integers that sum to a given value.

Given an array with integers and a number n, design an algorithm and write code to print all pairs of integers that sum up to this number.


Code input/output:
int [] A = {5, 9, 2, 11, 3, 8, 15, 7, 4, 12, 1};


Pairs that sum up to 12
5:7
9:3
11:1
8:4

Next Prime Number

Write code to find the next prime number after a given number.


Code input/output:

N: 14
Next Prime: 17


N: 293
Next Prime: 307


N: 3559
Next Prime: 3571

Print nodes of a BST at a given depth on the same line.

Write code to print out a binary search tree, such that all nodes at a given depth are printed on the same line.

Approach:
This problem is basically asking us to do the breadth First Search of the BST, such that all the nodes at a particular level are printed in new line.


Have a queue data structure.
init by adding root node ie 8 in the queue, then add a marker node which contains "null" elements.
when we dequeue any element from the queue, if its a normal node in the binary search tree then print it and add its not null left & right nodes to queue.
If we get a marker node then print a new line and add it back again to the queue if its not empty.



Code input and output:
int [] A = {8, 3, 10, 1, 6, 14, 4, 7, 13};


Printing inorder recursively: 
1 3 4 6 7 8 10 13 14 
Printing level order traversal of BST: 
8 
3 10 
1 6 14 
4 7 13 

nth to last element in a singly linked list.

Write code to return the nth to last element in a linked list.


Approach:
Take 2 pointers front and back.
init front and back with head of the singly link list.
then move front node to nth position.
After that move both front and back at the same time till front.next == null;
back pointer will be pointing to the nth node from end of the singly link list.
P.S. watch out for edge cases.


Code output:
58 -> 57 -> 38 -> 17 -> 83 -> 62 -> 86 -> 52 -> 67 -> 50 -> 49 -> 66 -> 34 -> null
8th node from end: 62

Print all the anagrams for a word from dictionary.

Imagine you had a dictionary. How would you print all anagrams of a word? What if you had to do this repeatedly? Could you optimize it?


Approach:
We need to develop a key for a given word such that all the words in an anagram set can be represented uniquely.
one way is to convert the word string to lowecase and sort the words lexicographically.
example: Tea, Eat, Ate will become: aet.
Then we can use a HashMap to store the anagram set, with "aet" as key and "Tea, Eat, Ate" as the list of words.


Another approach could be we can assign each letters from a..z a prime numbers (2, 3, 5, 7, 11, 13, 17, 19, 23, 29, .. so on)
and then for any word, we can calculate its key as the multiples of all the prime number corresponding to characters in the word.


say tea = 71*11*2 = 1562
similarly eat and ate will yeild 1562. Now 1562 is the key in your hashMap and value will be the list of words - "tea, eat, ate";


a=2, b=3, c=5, d=7, e=11, f=13, g=17, h=19, i=23, j=29, 
k=31, l=37, m=41, n=43, o=47, p=53, q=59, r=61, s=67, t=71, 
u=73, v=79, w=83, x=89, y=97, z=101


If we have to do the operation repeatedly then we will preprocess and calculate all the anagrams sets in the dictionary and cache it.

Find a line that intersects max number of points in a plane.

Given a bunch of points, how would you find the line which intersects the most number of points? Write pseudo-code for this algorithm.


Approach:


S = {p1,p2,p3,p4 ..., pn}
Where each point pi = {x, y} coordinates.


for every pair of Pi and Pj calculate:
Equation of line is: y = m*x + b
calculate slope m = (yj-yi)/(xj-xi)
also calculate y intercept b = (yi - m*xi)


Now, have a HashMap with key, value as HashMap H = <slope, <HashMap<y-intercept, count>>
Let G = HashMap<y-intercept, count>;


So for every pair of points we will calculate slope and y-intercept.
First we find if the slope already exists in the hashMap H and then we will check if the y-intercept exists in the 
hash G, if so then increment the counter C.
The Max counter Ci with slope mi and y-intercept bi is the answer.
ie y = mi * x + bi;

Find k closest stars in 3D space.

You have a huge set of stars as three dimensional coordinates. How would you find the k closest stars?


Approach:
S1 = {x1,y1,z1};
S2 = {x2,y2,z2};
S3 = {x3,y3,z3}; and so on..


1. First sort S[1..n] according to x coordinate. Then for every S[i] find the distance from k points in the front and then k points in the back by maintaing a max-heap of size k.
2. Secondly sort S[1..n] according to y coordinate. Then for every S[i] find the distance from k points in the front and k points in tha back and updating the k-size max-heap defined above if required.
3. Now sort S[1..n] according to z coordinate. And for every S[i] find the distance from k points in the front and k points in tha back and update the k-size max-heap if required.
4. Finally, k sized max-heap is the closed k stars.


Total complexity: 3nlogn + 6kn + 5klogk.
Considering k << n, we have: O(nlogn).

Merge 2 Sorted Arrays, such that integer in both array is copied once.

Write code to merge two arrays in sorted order such that if an integer is in both arrays, it only gets put into the new array once. 
What if you knew that one array was much longer than the other? Could you optimize it?


Input Arrays with repeated elements:
int [] A = {1, 1, 2, 2, 3};
int [] B = {2, 3, 3, 4};
Output:
Merged Array: 
1 1 2 2 3 3 4 


Input Arrays with unique elements:
int [] C = {2, 5, 7, 9, 10, 11};
int [] D = {1, 3, 5, 7, 8, 9, 11, 13};
Merged Array: 
1 2 3 5 7 8 9 10 11 13 


time complexity: O(lenA+lenB) = O(m+n).
space complexity: O(m+n);


Suppose array A is much larger than array B.
Now, take B[0] and do binary search in A for B[0].
If we find it at index i, then copy the data A[0]..A[i] to C;
Otherwise find index i in A, such that A[i] is less than B[0] and A[i+1] is greater than B[0].
Copy A[0]..A[i] to C and then copy B[0] to C at k=i+1;


Now, lets take B[1] and again do binary search for B[1] in A.
if we find it at index j, then copy A[i+1]..A[j] to C.
Otherwise find index j in A, such that A[j] < B[1] and A[i+1] > B[0].
Copy A[i+1]...A[j] to C and then copy B[1] to C at k=j+1;


So on...
suppose n = A.length; and m = B.length;
time complexity: O(m log n)
space complexity: O(m+n)

Rank of a node in a Order Statistic Binary Tree

You have a binary tree where each node knows the number of nodes in its sub-tree (including itself). Given a node n and an int k, write a function to return the kth node in an in-order traversal. Can you do this non-recursively?

Number of connections on web server in last 1 minute.

Write a data structure to count number of connections on web server in last 1 minute.

Approach:

Use a circular array of size say 60 with cumulative connections stored in indices. 

To calculate how many connections are on web server in last minute, just take difference between the current index and the previous one.

At any point, suppose you are storing the connections at index i, then reset i+1 to 0. 

Code output:

Server Connections in last 1 min: 3

3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Server Connections in last 1 min: 2500473

4042037 8366214 12750825 17069356 21435609 25818813 30193316 34585084 38981930 43362517 47729398 51954656 56319336 60718454 65115406 69495682 73891294 78291081 82663083 85163556 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Server Connections in last 1 min: 1673643

4042037 8366214 12750825 17069356 21435609 25818813 30193316 34585084 38981930 43362517 47729398 51954656 56319336 60718454 65115406 69495682 73891294 78291081 82663083 86993284 91375051 95752355 100071358 104330554 108415170 112538285 116863280 121258700 125587403 129942011 134230253 138600661 142938928 147332572 151699763 156056115 160386707 164517422 168667052 170340695 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 

Server Connections in last 1 min: 1937344

0 8366214 12750825 17069356 21435609 25818813 30193316 34585084 38981930 43362517 47729398 51954656 56319336 60718454 65115406 69495682 73891294 78291081 82663083 86993284 91375051 95752355 100071358 104330554 108415170 112538285 116863280 121258700 125587403 129942011 134230253 138600661 142938928 147332572 151699763 156056115 160386707 164517422 168667052 172844039 177046285 181257855 185477645 189761265 193999235 198216330 202498034 206710346 210913720 215265043 219554608 223756476 228036400 232286104 236596081 240862590 245114846 249370034 253580282 255517626 

Server Connections in last 1 min: 1165884

261960600 266156936 270515554 274897599 279280497 283664192 288055183 292439077 296814993 301208147 305548693 309453194 313561569 317817387 322058006 326376381 330750504 335138909 339517887 340683771 0 95752355 100071358 104330554 108415170 112538285 116863280 121258700 125587403 129942011 134230253 138600661 142938928 147332572 151699763 156056115 160386707 164517422 168667052 172844039 177046285 181257855 185477645 189761265 193999235 198216330 202498034 206710346 210913720 215265043 219554608 223756476 228036400 232286104 236596081 240862590 245114846 249370034 253580282 257793064 

Server Connections in last 1 min: 3375382

261960600 266156936 270515554 274897599 279280497 283664192 288055183 292439077 296814993 301208147 305548693 309453194 313561569 317817387 322058006 326376381 330750504 335138909 339517887 343893181 348271766 352634531 356957672 361256457 365595987 369933329 374262314 378625770 382977564 387371854 391741255 396148986 400533862 404908812 409300391 413695463 418093979 422477882 425853264 0 177046285 181257855 185477645 189761265 193999235 198216330 202498034 206710346 210913720 215265043 219554608 223756476 228036400 232286104 236596081 240862590 245114846 249370034 253580282 257793064 

Server Connections in last 1 min: 902289

261960600 266156936 270515554 274897599 279280497 283664192 288055183 292439077 296814993 301208147 305548693 309453194 313561569 317817387 322058006 326376381 330750504 335138909 339517887 343893181 348271766 352634531 356957672 361256457 365595987 369933329 374262314 378625770 382977564 387371854 391741255 396148986 400533862 404908812 409300391 413695463 418093979 422477882 426851222 431242526 435636157 440017329 444408215 448769117 453168222 457561690 461906594 466303078 470703003 475091017 479476932 483871156 488262033 492585214 496985526 501373444 505753642 510117476 511019765 0 

Server Connections in last 1 min: 2864165

523295700 527683139 532078847 536464008 540855095 545243156 549635094 554029949 558416866 562810843 567209609 571430001 575788814 580182347 584562119 588946702 593321752 596185917 0 343893181 348271766 352634531 356957672 361256457 365595987 369933329 374262314 378625770 382977564 387371854 391741255 396148986 400533862 404908812 409300391 413695463 418093979 422477882 426851222 431242526 435636157 440017329 444408215 448769117 453168222 457561690 461906594 466303078 470703003 475091017 479476932 483871156 488262033 492585214 496985526 501373444 505753642 510117476 514504603 518899160 

Rotate a square matrix counter clockwise by 90 degrees.

Given a KxK array, rotate the array 90 degrees counter-clockwise in place.


Code output:



Original Square Matrix: 
1 2 3 4 
5 6 7 8 
9 10 11 12 
13 14 15 16 


Transpose of the square matrix: 
1 5 9 13 
2 6 10 14 
3 7 11 15 
4 8 12 16 


Matrix Rotated by 90 degrees counter clockwise:
4 8 12 16 
3 7 11 15 
2 6 10 14 
1 5 9 13 

Dynamic Programming: Water Tank Problem.

you are given following:
1. An empty tank
2. Unlimited source of water.
3. Some container of certain measurments and a container of 1 litre is always given.


Your job is to fill the tank from source of water using the containers in minimum number of steps.
You cant fill the container with a small amount of water than its size (filling partially is not allowed).
Find the number of steps and print the solution.


e.g.
Tank Size: 80 litre
Containers: 1,3,5,6,25 litre
Solution:
4
5,25,25,25


Tank Size: 71 litre
Containers: 1,3,5,6,25 litre
Solution:
6
3,6,6,6,25,25

Approach:
This problem is similar to the coin change problem, where the number of denominations is infinite.
Please refer:
http://karmaandcoding.blogspot.in/2012/01/coin-change-problem-with-limit-on.html

Code:

int [] container = {1, 3, 5, 6, 25};

fillTheTank(container, 80);
fillTheTank(container, 71);


Output:

Number of containers for 80: 4
25 25 25 5 
Number of containers for 71: 6
25 25 6 6 6 3 

1D Array into 2D table.

You are given a 1D array of integers, such as:
int[] array = [3,4,7,2,2,6,0,9];
Suppose you need to treat this array as a 2D table with a given number of rows.
You want to sum the columns of the table.
One value of numRows is 4..in that case the resultant array would look like
3 4
7 2
2 6
0 9
—-
12 21

Minimum distance between 2 elements in an array with duplicates.

Consider there is an array with duplicates and u r given two numbers as input and u have to return the minimum distance between the two in the array with minimum complexity.

Input Array:

int [] A = {1, 5, 3, 7, 2, 8, 3, 4, 5, 9, 9, 3, 1, 3, 2, 9};

 minDist = minDistance(A, 9, 3);

System.out.println("Min Distance (9, 3): " + minDist);

minDist = minDistance(A, 3, 9);

System.out.println("Min Distance (3, 9): " + minDist);

minDist = minDistance(A, 4, 7);

System.out.println("Min Distance (4, 7): " + minDist);

minDist = minDistance(A, 9, 9);

System.out.println("Min Distance (9, 9): " + minDist);

minDist = minDistance(A, 3, 3);

System.out.println("Min Distance (3, 3): " + minDist);

minDist = calcMinDistance(A, 5, 8);

System.out.println("Min Distance (5, 8): " + (minDist-1));

minDist = calcMinDistance(A, 5, 9);

System.out.println("Min Distance (5, 9): " + (minDist-1));

Output:

Min Distance (9, 3): 0

Min Distance (3, 9): 0

Min Distance (4, 7): 3

Min Distance (9, 9): 0

Min Distance (3, 3): 1

Min Distance (5, 8): 2

Min Distance (5, 9): 0

Dynamic Programming: Bounded (1/0) knapsack problem.

This problem is also known as Integer Knapsack Problem (Duplicate Items Forbidden).


During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or knapsack) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1.....wn and dollar value v1.....vn. What's the most valuable combination of items he can fit into his bag?


For instance, take Capacity = 10 and
Item Weight Value
1            6      $30
2            3      $14
3            4      $16
4            2      $9


Here repitition is not allowed.


K(w,j) be the max value achievable using knapsack of size w and items 1....j
The answer we seek is K(w,n)


Lets try to express K(w,j) in terms of smaller subproblems
Now here, either j is needed to solve the subproblem or its not needed.
So we have,
K(w,j) = Max { K(w - w[j], j-1) + v[j], K(w, j-1)}


Now algorithm involves, filling out a 2-D table with W+1 rows and n+1 columns.
Time complexity: O(nW).


Code Input:
int [] W = {6, 3, 4, 2};
int [] V = {30, 14, 16, 9};
int C = 10;


Output:
Optimal value for integer knapsack: 46

Dynamic Programming: Unbounded knapsack problem

During a robbery, a burglar finds much more loot than he had expected and has to decide what to take. His bag (or knapsack) will hold a total weight of at most W pounds. There are n items to pick from, of weight w1.....wn and dollar value v1.....vn. What's the most valuable combination of items he can fit into his bag?


For instance, take W = 10 and
Item Weight Value
1            6      $30
2            3      $14
3            4      $16
4            2      $9


Let K(w) = max value achievable with a knapsack of capacity w.


Now if the optimal solution to K(w) includes i, then removing this item from knapsack leaves an optimal solution to K(w-w[i])+v[i], for some i.
As we dont know which i, so we will try all the possibilities.
K(w) = MAX {K(w-w[i] + v[i]} for i:w[i]<w


The maximum over an empty set is 0.


K(0) = 0
for w = 1 to W:
K(w) = max{K(w - wi) + vi: wi <= w}
return K(W)




This algorithm fills in a one-dimensional table of length W + 1, in left-to-right order. Each entry can take up to O(n) time to compute, so the overall running time is O(nW). As always, there is an underlying dag. Try constructing it, and you will be rewarded with a startling insight: this particular variant of knapsack boils down to finding the longest path in a dag!


Code Input:
int [] W = {6, 3, 4, 2};
int [] V = {30, 14, 16, 9};
int M = 10;


Code output:
Printing knapsack for different Ws:
0 0 9 14 18 23 30 32 39 44 48 
Optimal value for unbounded knapsack: 48