Hi. I'm currently trying to solve this problem, and since I can't solve it, I looked at the editorial.
It said: Let V be the largest coin value, and call this type of coin silver and all other coins brass. It is not difficult to prove that for any change amount of at least V^2, it is possible to use at least one silver coin (hint: consider the partial sums modulo V), and hence that in making change of at least 2V^2 there can be at least V silver coins. Now if Farmer John pays at least 2V^2, and hence pays with V coins, then a similar argument shows that some set of them adds up to a multiple of V and at most V^2, which can be cancelled out with the silver coins in the change. So the change amount can never exceed 2V^2.
What does this mean? And how do we prove this?
First let's imagine knapsack problem modulo V. We want to show that we can achieve every modulo with a multiset of coins, such that the sum of the coins < V^2.
Let's prove it by contradiction. Consider a set with sum S >= V^2, and it is impossible to make any multiset of coins with sum S-V, S-V*2, S-V*3 etc...
Let this multiset be x1, x2 ... xK. Because the sum is at least V^2, K >= V.
We will prove that we can find some subset of them such that their sum is divisible by V.
Let's consider the prefix sum values: x1, x1+x2, x1+x2+x3 ... (x1+x2+...+xK). If one of these prefix sums is divisible by V, then this is our required subset. Otherwise, all of them are only from the set {1, 2, ..., V-1}. So there are V-1 possiblities for V prefix sums. By the pigeonhole principle at least two of them are the same. Then, we just take the contiguous array between these two same ones, and this will have sum divisible by V. Try some examples if it's not clear.
Therefore we can remove some subset divisible by V and achieve a multiset with sum S — V*P for some P. This is a contradiction to our initial assumption. So therefore you can achieve all modulo V subset sums, with only multisets with sum < V^2. We have also proved that for all multisets of size >= V^2, there is at least one V coin.
Okay, now we will use this to solve the problem. Suppose Farmer John gets X dollars in change, X >= 2V^2 + V. Now, first of all, it is helpful to visualise it as a stack of different sized blocks, where each coin is a block with height equal to its worth. Now visualise height T (the target) on this stack of blocks. It 'cuts' one coin in half, but apart from that, all the coins fully above T are intact. Notably, the sum of the coins fully above T is at least 2V^2 because X >= 2V^2 + V. (the second V value is because we must ignore the coin split in half by T).
Out of the black blocks, sum is at least V^2 (actually 2V^2, but only consider V^2), so we have proved there is at least one subset of black blocks divisible by V.
Also, the amount of change >= 2V^2. So there are at least V^2 in only V coins on the right blue side. So therefore we remove the black subset, and the appropriate amount of blue V-coins to counteract that subset.
Then we have a more optimal solution. Therefore the most optimal solution has less than 2V^2 change.
Thanks, I understand now.