Given a List of coins, find minimum number of coins that need to be added to list so that all prices from [1,P] can be paid using the coins of list.
Constraints Length of coin list<=100000 Value of coins <=1000 P<=10000
Sample: P=19 Coinlist={1,4,10} solution=2
This may be solved with DP, but it does not need to be. There is a greedy solution based on the necessary condition on whether a prefix of the increasingly sorted coin list with sum $$$S$$$ can make up all subset sums in $$$[1,S]$$$.
any links for the question you mentioned, would be helpful
I remember solving a task almost equal to the task I explained, but I forgot the link to it. I'll update the comment if I find it out. Anyways the main theorem and the proof is as follows if you were wondering.
WLOG assume that $$$a$$$ is sorted (sort it if it isn't). Assume for some prefix $$$a_1,a_2,\cdots,a_k$$$ the sum is $$$S_k$$$, and it generates all integers in $$$[0,S_k]$$$. Then $$$a_{k+1}$$$ must be equal to or less than $$$S_k+1$$$ for the new prefix $$$a_1,a_2,\cdots,a_{k+1}$$$ to generate all subset sum in $$$[0,S_k+a_{k+1}]$$$. We can prove this by contradiction. If $$$a_{k+1} \ge S_k+2$$$, then we cannot generate the integer $$$S_k+1$$$, and thus $$$a_{k+1}$$$ is at most $$$S_k+1$$$. If $$$a_{k+1} \le S_k+1$$$, then we can trivially generate the integers in the range $$$[a_{k+1},S_k+a_{k+1}]$$$. As the two ranges are continuous, we conclude that we can generate every integer in $$$[0,S_k+a_{k+1}]$$$. Thus, $$$a_{k+1} \le S_k+1$$$ is both necessary and sufficient to generate all subset sums in $$$[0,S_k+a_{k+1}]$$$.
UPD: the task was "No change" from EIO 2020-21
if you have coinst with value 1 and 2 why can't you make all the coins
Number of times a value is present in coin list, that value can be used only that many times
let the array be arr (0 indexed) , and the corresponding prefix sum array be pre (in the pseudo code , prefix sum array is considered as 0 indexed) here is the pseudo code