Proof of optimal choice in UVA food portion sizes problem ?

Revision en2, by mohamedeltair, 2017-09-27 02:20:40

Regarding this problem in UVA: Food portion sizes I know that the optimal S will be either arr[i]/1 or arr[i]/2 or arr[i]/3, where 1 <= i <= n and arr[i] is the required food for ith person, that is we try all arr[i]/1, arr[i]/2, arr[i]/3 for all i and choose the one which gives minimum result. I know that these three choices are the minimum choices in terms of cost for the ith person, but why choosing one of them from one of the n persons results in a minimum total result for all people ? what is the proof for this ?


  Rev. Lang. By When Δ Comment
en2 English mohamedeltair 2017-09-27 02:20:40 21
en1 English mohamedeltair 2017-09-27 02:17:17 660 Initial revision (published)