Coin change, no solution?

Revision en1, by alex_ita, 2020-08-17 14:58:49

Hello. I recently had an interview and have been given a weird problem. I have a number M (up to 10⁹) and array of size 1000. I have to return SUBSET whose sum is the largest possible but not greater than M. Naturally, I wanted to code it like coin change or knapsack, but it fails in either memory or time. Any ideas?

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en2 English alex_ita 2020-08-18 02:56:05 272
en1 English alex_ita 2020-08-17 14:58:49 345 Initial revision (published)