Question:
Find if its possible to make up a integer (say N) with 21,19 and 37?
a. N will be provided as input
b. You can use only these three numbers: 27,19,37
c. Only multiplication, addition, repetition and replacement are allowed
For example:
Input: 24, Output: not possible
Input: 94, Output: possible - 94 = 19*3 + 37
My Queries:
I'd appreciate could you make yourself a little more flexible to explain in terms of DP / Greedy / Div & Con equations and explain your thought process.
As, for example, in Longest Common Subsequence we use the following:
//assuming X[i.....m] and Y[j.....n]
LCS(i,j) = {
0 , when i = m or j=n
Max { LCS(i, j+1) , LCS(i+1, j) } when X[i] ≠ Y[j]
1+ LCS(i+1,j+1) when X[i] == Y[j]
}
It is same as the Knapsack problem with following parameters :-
W = Knapsack capacity = N
items = 19 ( N/19 times), 27 (N/27 times), 37 (N/37 times).
Cost & weight of items are same.
Maximize profit. If maximum profit equals N then it is possible to construct N using 19,27,37
There is a DP solution of Knapsack problem : -
Note: You should study Knapsack problem by yourself donot end up posting another question for its code.