Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @flopy78,validated by @June1664,@LeMasSon and @BlasphemousCrossbree.
If you have any issues, feel free to ping them.
Test case 2
1 2 20 50 100
63
Given answer
20 20 20 2 1
Why the answer is not this?
50 2 2 2 2 2 2 1
He has opened a shop and wants to give change to his customers using the fewest coins possible.
The given answer uses 5 coins while yours uses 8.
Got it. Thanks.
The answer you propose would be the one of a greedy algorithm, but it’s not always the best one if some denominations are missing…
Here think about using BFS !
BFS could work but troublesome to keep the states between branches, and easy to do too much branching.
I tried a different approach to reduce the search space to the minimum then brute-force all remaining possibilities. (In most cases it is less than a hundred, or even less than ten.)
For example when the goal is 63 and we have $1 and $2 coins. It is unnecessary to try $1x63, $1x62, $1x61…
The solution should contain either $1 x 0 or $1 x 1.
I guess it is fast enough to handle 100+ denominations and a thousand times higher goal values.
Experiment with a larger dataset, 200 denominations:
3 5 6 7 17 33 38 41 43 44 52 53 56 58 67 71 80 82 83 94 95 96 97 115 139 148 151 159 160 161 173 180 181 184 191 193 199 200 201 202 205 206 211 212 213 220 224 229 233 238 242 243 254 255 259 260 261 262 263 264 268 274 282 299 302 314 317 321 323 325 326 333 340 343 349 355 360 362 364 369 372 373 377 379 390 391 392 395 402 404 417 422 434 437 443 461 466 469 472 473 478 481 490 491 496 506 509 511 516 519 524 527 528 535 539 547 553 561 567 580 588 592 595 604 608 611 619 620 621 640 651 654 655 657 661 667 670 672 674 677 680 688 691 697 698 700 701 706 716 719 720 724 742 746 753 758 766 769 774 780 784 788 790 797 809 818 826 827 829 835 837 840 844 845 850 852 863 868 871 886 896 897 899 908 917 925 940 943 949 952 958 961 966 978 980 982 983 988 991 997
6341
Solution:
991 991 991 991 991 991 395
Hello java_coffee_cup,
From what I understand of the concept of highest denomination, shouldn’t the result be “997 997 997 997 997 983 373” instead?
Let me reply this post…
Hi @cg123 You are correct!
I was suspecting there is such a case to happen I should have taken care of.
In the puzzle none of the test cases were testing this property (where 6341/997 = 6 but we use only 5x997 to get optimum solution) so I have not implemented it yet.
Could the puzzle author add a few test cases similar to this one, within the constraints?