coins {1, 7, 10}, amounts 1..30
  x  greedy              #g  optimum             #o
  1  1                    1  1                    1
  2  1+1                  2  1+1                  2
  3  1+1+1                3  1+1+1                3
  4  1+1+1+1              4  1+1+1+1              4
  5  1+1+1+1+1            5  1+1+1+1+1            5
  6  1+1+1+1+1+1          6  1+1+1+1+1+1          6
  7  7                    1  7                    1
  8  7+1                  2  1+7                  2
  9  7+1+1                3  1+1+7                3
 10  10                   1  10                   1
 11  10+1                 2  1+10                 2
 12  10+1+1               3  1+1+10               3
 13  10+1+1+1             4  1+1+1+10             4
 14  10+1+1+1+1           5  7+7                  2   <- greed loses
 15  10+1+1+1+1+1         6  1+7+7                3   <- greed loses
 16  10+1+1+1+1+1+1       7  1+1+7+7              4   <- greed loses
 17  10+7                 2  7+10                 2
 18  10+7+1               3  1+7+10               3
 19  10+7+1+1             4  1+1+7+10             4
 20  10+10                2  10+10                2
 21  10+10+1              3  1+10+10              3
 22  10+10+1+1            4  1+1+10+10            4
 23  10+10+1+1+1          5  1+1+1+10+10          5
 24  10+10+1+1+1+1        6  7+7+10               3   <- greed loses
 25  10+10+1+1+1+1+1      7  1+7+7+10             4   <- greed loses
 26  10+10+1+1+1+1+1+1    8  1+1+7+7+10           5   <- greed loses
 27  10+10+7              3  7+10+10              3
 28  10+10+7+1            4  1+7+10+10            4
 29  10+10+7+1+1          5  1+1+7+10+10          5
 30  10+10+10             3  10+10+10             3
  amounts on which greed loses: 6 of 30; the smallest is 14

coins {1, 5, 8}, amounts 1..100
  amounts on which greed loses: 47 of 100; the smallest is 10
coins {1, 5, 10, 25}, amounts 1..100
  amounts on which greed loses: 0 of 100; greed is optimal on every amount tested
