From Algorithmist
Jump to navigation Jump to search

39. Piggy-bank[edit]



Given the weight of a piggy bank and the weights and values of individual coins that could be contained in the piggy bank, calculate the minimum sum of the values of the coins.



The first number T is the number of test cases to follow. Each test case begins with a line containing two integers representing the weight if the empty piggy bank and the weight of the full piggy bank respectively. The next line contains a single integer representing the number of lines to follow. The following lines contain two integers representing the value and the weight of the coin types respectively.

Modest Proposal[edit]

Establish an array with dimension F-E+1 which will hold the minimum possible sum of money for a particular weight. Iterate over each coin value which has weight less than current index in array (i.e. the current weight) and check if the sum of money after including current coin value is less than the current sum of money. If yes, then replace with new sum. Answer is the sum of money for index F-E in array.

10 110
1 1
30 50
10 110
1 1
50 30
1 6
10 3
20 4


The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.

External Links[edit]

  • Dynamic Programming - Wiki Link
  • Dynamic Programming Tutorial - Topcoder.com
  • Knapsack Problem