UVa 147

From Algorithmist

Contents 1 147 - Dollars 2 Summary 3 Explanation 4 Gotchas 5 Notes 6 Optimizations 7 Input 8 Output

[edit] 147 - Dollars

• http://acm.uva.es/p/v1/147.html

[edit] Summary

Count the number of ways we can form a certain amount.

[edit] Explanation

This is a standard Dynamic Programming - Subset Sum problem.

[edit] Gotchas

• Rounding Errors.

[edit] Notes

• Avoid using double in the input.
• The inputs have been raised in the recent years.

[edit] Optimizations

• You can make the array smaller by noting that everything is a multiple of 5 cents.

[edit] Input

0.20
2.00
299.90
0.00

[edit] Output

  0.20                4
  2.00              293
299.90  181000196059736