3

The Problem: On Venus, the Venusians use coins of these values [1, 6, 10, 19]. Use an algorithm to compute the minimum number of coins needed to make change for 42 on Venus. State which coins are used to satisfy this minimum

I used Dynamic Programming as the algorithm used to solve this problem.

Here my work 

  1 coin to make 6
  2 coins to make 12 (+6)
  3 coins to make 13 (+1)
  4 coins to make 32 (+19)
  5 coins to make 42 (+10)

So my answer would be the minimum number of coins needed to make change for 42 on Venus would be 5 and the coins to satisfy this minimum are {6, 6, 1, 19, 10}

Does everyone agree with my answer(5) and my arrangement of coins to satisfy the minimum 5 or is there a better answer?

committedandroider
  • 1,884

1 Answers1

1

I am contributing a Perl script and a table of values up to $57$ for verification purposes. This is the table.

1: 1
2: 1, 1
3: 1, 1, 1
4: 1, 1, 1, 1
5: 1, 1, 1, 1, 1
6: 6
7: 6, 1
8: 6, 1, 1
9: 6, 1, 1, 1
10: 10
11: 10, 1
12: 6, 6
13: 6, 6, 1
14: 6, 6, 1, 1
15: 6, 6, 1, 1, 1
16: 10, 6
17: 10, 6, 1
18: 6, 6, 6
19: 19
20: 19, 1
21: 19, 1, 1
22: 10, 6, 6
23: 10, 6, 6, 1
24: 6, 6, 6, 6
25: 19, 6
26: 19, 6, 1
27: 19, 6, 1, 1
28: 10, 6, 6, 6
29: 19, 10
30: 19, 10, 1
31: 19, 6, 6
32: 19, 6, 6, 1
33: 19, 6, 6, 1, 1
34: 10, 6, 6, 6, 6
35: 19, 10, 6
36: 19, 10, 6, 1
37: 19, 6, 6, 6
38: 19, 19
39: 19, 19, 1
40: 19, 19, 1, 1
41: 19, 10, 6, 6
42: 19, 10, 6, 6, 1
43: 19, 6, 6, 6, 6
44: 19, 19, 6
45: 19, 19, 6, 1
46: 19, 19, 6, 1, 1
47: 19, 10, 6, 6, 6
48: 19, 19, 10
49: 19, 19, 10, 1
50: 19, 19, 6, 6
51: 19, 19, 6, 6, 1
52: 19, 19, 6, 6, 1, 1
53: 19, 10, 6, 6, 6, 6
54: 19, 19, 10, 6
55: 19, 19, 10, 6, 1
56: 19, 19, 6, 6, 6
57: 19, 19, 19

This is the Perl script that I used. It is left as an exercise to the reader to modify this script or possibly use a different programming language so that it collects all minimal solutions rather than just one.

#! /usr/bin/perl -w

 MAIN: {
     my @coins = (1, 6, 10, 19);
     my $upper = shift || 42;

     my @change = ([]);

     for(my $q=1; $q <= $upper; $q++){
         my ($count, $denom) = ($q+1);

         foreach my $coin (@coins){
             my $rest = $q-$coin;

             if($rest >= 0){
                 my $restcount = scalar(@{ $change[$rest]});
                 if($restcount + 1 < $count){
                     $denom = $coin;
                     $count = $restcount + 1;
                 }
             }
         }

         my $bestchange = [@{ $change[$q-$denom] }, $denom];
         push @change, $bestchange;
     }

     for(my $q=1; $q <= $upper; $q++){
         print "$q: ";
         print join(', ', @{ $change[$q] });
         print "\n";
     }
}

Addendum. Here is the version that collects all solutions. This is only interesting for small values since the greedy type behavior dominates with larger values.

#! /usr/bin/perl -w
#

 MAIN: {
     my @coins = (1, 6, 10, 19);
     my $upper = shift || 42;

     my @change = ([[]]);

     for(my $q=1; $q <= $upper; $q++){
         my ($count, $denom) = ($q+1, []);

         foreach my $coin (@coins){
             my $rest = $q-$coin;

             if($rest >= 0){
                 my $restcount = 
                     scalar(@{ $change[$rest]->[0]});
                 if($restcount + 1 < $count){
                     $denom = [$coin];
                     $count = $restcount + 1;
                 }
                 elsif($restcount + 1 == $count){
                     push @$denom, $coin;
                 }
             }
         }

         my $bestchange = [];

         foreach my $dn (@$denom){
             foreach my $ch (@{ $change[$q-$dn] }){
                 push @$bestchange, [ @$ch, $dn ]
                     if scalar(@$ch) == 0 ||
                     $ch->[-1] <= $dn;
             }
         }

         push @change, $bestchange;
     }

     for(my $q=1; $q <= $upper; $q++){
         print "$q: ";
         my @sols = 
             map { "[" . join(', ', @$_) . "]" }
             @{ $change[$q] };
         print join(', ', @sols);
         print "\n";
     }
}

This is the table that was computed.

1: [1]
2: [1, 1]
3: [1, 1, 1]
4: [1, 1, 1, 1]
5: [1, 1, 1, 1, 1]
6: [6]
7: [1, 6]
8: [1, 1, 6]
9: [1, 1, 1, 6]
10: [10]
11: [1, 10]
12: [6, 6]
13: [1, 6, 6]
14: [1, 1, 6, 6]
15: [1, 1, 1, 6, 6]
16: [6, 10]
17: [1, 6, 10]
18: [6, 6, 6]
19: [19]
20: [10, 10], [1, 19]
21: [1, 10, 10], [1, 1, 19]
22: [6, 6, 10]
23: [1, 6, 6, 10]
24: [6, 6, 6, 6]
25: [6, 19]
26: [6, 10, 10], [1, 6, 19]
27: [1, 6, 10, 10], [1, 1, 6, 19]
28: [6, 6, 6, 10]
29: [10, 19]
30: [10, 10, 10], [1, 10, 19]
31: [6, 6, 19]
32: [6, 6, 10, 10], [1, 6, 6, 19]
33: [1, 6, 6, 10, 10], [1, 1, 6, 6, 19]
34: [6, 6, 6, 6, 10]
35: [6, 10, 19]
36: [6, 10, 10, 10], [1, 6, 10, 19]
37: [6, 6, 6, 19]
38: [19, 19]
39: [10, 10, 19], [1, 19, 19]
40: [10, 10, 10, 10], [1, 10, 10, 19], [1, 1, 19, 19]
41: [6, 6, 10, 19]
42: [6, 6, 10, 10, 10], [1, 6, 6, 10, 19]
43: [6, 6, 6, 6, 19]
44: [6, 19, 19]
45: [6, 10, 10, 19], [1, 6, 19, 19]
46: [6, 10, 10, 10, 10], [1, 6, 10, 10, 19], [1, 1, 6, 19, 19]
47: [6, 6, 6, 10, 19]
48: [10, 19, 19]
49: [10, 10, 10, 19], [1, 10, 19, 19]
50: [6, 6, 19, 19]
51: [6, 6, 10, 10, 19], [1, 6, 6, 19, 19]
52: [6, 6, 10, 10, 10, 10], [1, 6, 6, 10, 10, 19], [1, 1, 6, 6, 19, 19]
53: [6, 6, 6, 6, 10, 19]
54: [6, 10, 19, 19]
55: [6, 10, 10, 10, 19], [1, 6, 10, 19, 19]
56: [6, 6, 6, 19, 19]
57: [19, 19, 19]
Marko Riedel
  • 61,317