Find if it's possible to make up a integer with some given numbers

Question

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:

1. Can you please help me in this assignment to show the path of DP / Div & Con / Greedy?
2. Which one shall I choose and why not the others (in this case)?

3. 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]
   }
   

Answer 1

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 : -

Knapsack Problem

Note: You should study Knapsack problem by yourself donot end up posting another question for its code.