Return to Answer

You can do better than the greedy algorithm. With coins of value

{1, 6, 20, 75, 175, 474, 756, 785}

you can get N =

3356.

I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:

one coin: {1}, N = 1
two coins: {1, 2}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388
seven coins: {1, 7, 18, 62, 104, 244, 259} or {1, 8, 13, 66, 115, 254, 415}, N = 1137

You can do better than the greedy algorithm. With coins of value

{1, 6, 20, 75, 175, 474, 756, 785}

you can get N =

3356.

I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:

one coin: {1}, N = 1
two coins: {1, 2} or {1, 3}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388
seven coins: {1, 7, 18, 62, 104, 244, 259} or {1, 8, 13, 66, 115, 254, 415}, N = 1137

You can do better than the greedy algorithm. With coins of value

{1, 6, 20, 75, 175, 474, 756, 785}

you can get N =

3356.

I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are the unique optimal solutions for up through six coins:

one coin: {1}, N = 1
two coins: {1, 2}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388

You can do better than the greedy algorithm. With coins of value

{1, 6, 20, 75, 175, 474, 756, 785}

you can get N =

3356.

I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are all the optimal solutions for up through seven coins:

one coin: {1}, N = 1
two coins: {1, 2}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388
seven coins: {1, 7, 18, 62, 104, 244, 259} or {1, 8, 13, 66, 115, 254, 415}, N = 1137

You can do better than the greedy algorithm. With coins of value

{1, 7, 16, 51, 125, 313, 755, 956}

you can get N =

3302.

I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are the unique optimal solutions for up through six coins:

one coin: {1}, N = 1
two coins: {1, 2}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388

You can do better than the greedy algorithm. With coins of value

{1, 6, 20, 75, 175, 474, 756, 785}

you can get N =

3356.

I wrote a search program for this but it isn’t going to finish searching the entire space in reasonable time, so I don’t know whether that’s optimal. Here are the unique optimal solutions for up through six coins:

one coin: {1}, N = 1
two coins: {1, 2}, N = 4
three coins: {1, 4, 5}, N = 15
four coins: {1, 3, 11, 18}, N = 44
five coins: {1, 4, 9, 31, 51}, N = 126
six coins: {1, 7, 11, 48, 83, 115}, N = 388