Tävlingsprogrammering/Uppgifter/Colaautomat
Colaautomat
På mitt jobb finns en colaautomat där en burk Coca-Cola kostar 8 kr. Maskinen har ett myntinkast som accepterar 1 kr, 5 kr och 10 kronorsmynt. Efter att tillräckligt många mynt har stoppats in kan jag trycka på Cola-knappen och få ut en Cola och eventuell växel. Växeln ges alltid tillbaka med det minsta antalet möjliga mynt. Denna procedur upprepas tills jag köpt så många Cola-burkar som jag vill ha. Jag kan bara köpa en burk åt gången. Om jag t.ex. skulle stoppa in 16 kr och trycka på Cola-knappen skulle jag få ut en burk och 8 kronor i växel (en 5-krona och 3 enkronor).
Givet hur många burkar jag vill köpa, samt hur många mynt jag har av varje valör, vad är det minsta antalet mynt jag behöver stoppa in i maskinen för att köpa så många burkar som jag vill ha? Jag kan ta upp mynt som kommer ut som växel. Du kan utgå ifrån att maskinen har obegränsat med mynt i växel.
Programmet ska, i tur och ordning, fråga efter hur många Cola-burkar jag vill köpa (mellan 1 och 40), antalet 1-kronors mynt jag har (mellan 0 och 100), antalet 5-kronors mynt (mellan 0 och 20), och antalet 10-kronors mynt (mellan 0 och 10). Programmet ska skriva ut det minsta antal mynt jag behöver stoppa i myntinkastet. Du kan utgå ifrån att jag har tillräckligt med pengar för att köpa alla Cola-burkar jag vill ha.
Körningsexempel:
Antal burkar ? 2 Antal 1-kronor ? 2 Antal 5-kronor ? 1 Antal 10-kronor ? 1 Du behöver stoppa in 5 mynt.
Förklaring: Först stoppar jag in en 10-krona och trycker på Cola-knappen. Ut kommer första burken och två enkronor. Därefter stoppar jag in 5-kronan och tre enkronor (en av dessa kommer från föregående växel). Totalt måste jag stoppa in 5 mynt.
Lösning
[redigera]Djupsökning är ett enkelt alternativ här. Vi har två specialfall som ger färre mynt för mer cola:
1 tia och 3 enkronor; 2 femmor och 3 enkronor
Vi använder oss utav en cache för att inte beräkna utifrån samma värde mer än nödvändigt.
#include <iostream>
#include <algorithm>
unsigned int nMin = ~0;
int nCache[41][101][21][11];
void DFS(const int& nMynt, const int& nBurkar, const int& n1, const int& n5, const int& n10) {
if (nBurkar == 0) {
if (nMin > nMynt)
nMin = nMynt;
return;
}
if (nCache[nBurkar][n1][n5][n10] != -1) {
if (nCache[nBurkar][n1][n5][n10] <= nMynt) {
return;
}
}
nCache[nBurkar][n1][n5][n10] = nMynt;
if (n10 >= 1 && n1 >= 3)
DFS(nMynt+4, nBurkar-1, n1-3, n5+1, n10-1);
if (n5 >= 2 && n1 >= 3)
DFS(nMynt+2, nBurkar-1, n1+3, n5-2, n10);
if (n5 >= 1 && n1 >= 3)
DFS(nMynt+4, nBurkar-1, n1-3, n5-1, n10);
if (n10 >= 1)
DFS(nMynt+1, nBurkar-1, n1+2, n5, n10-1);
if (n5 >= 2)
DFS(nMynt+2, nBurkar-1, n1+2, n5-2, n10);
if (n1 >= 8)
DFS(nMynt+8, nBurkar-1, n1-8, n5, n10);
}
int main() {
int nBurkar, n1, n5, n10;
std::cin >> nBurkar >> n1 >> n5 >> n10;
std::fill(&nCache[0][0][0][0], &nCache[40][100][20][10], -1);
DFS(0, nBurkar, n1, n5, n10);
std::cout << nMin << '\n';
return 0;
}
Här nedan följer en iterativ lösning i Java. Rent spontant kan man känna att man vill använda sig av en girig algoritm, d.v.s. man försöker först köpa colaburkar med alla tior (för då förbrukar man ju bara ett mynt per cola), sedan försöker man köpa med två femmor, sedan med en femma och tre enkronor och slutligen med åtta enkronor. Dock dröjer det inte länge innan man inser att uppgiften nog inte är så enkel, men man ska inte misströsta för man har egentligen nästan kommit halvvägs.
Den enda "växlingshandling" som kan vara vettig att utföra är den där man stoppar i en tia och tre enkronor, vilket ger en femma i växel. Ponera t.ex. att vi ska köpa 3 burkar och vi har 1 tia, 1 femma och 20 enkronor, då kan det vara smart att utföra denna växling. (Handlingen två femmor och tre enkronor är fullkomligt värdelös, eftersom den bara ger tillbaka den ena av femmorna i växel.) Men när ska man då utföra denna handling? Jo när följande två krav är uppfyllda:
- Man kan (hinner) inte komma fram till målet genom att bara använda tior (en åt gången) och femmor (två åt gången), utan man behöver använda åtta enkronor åt gången för att köpa de sista burkarna (vilket man vill undvika).
- Man har inte tillräckligt med femmor för att kunna uppnå målet med bara tior (en åt gången) och femmor (med en åt gången tillsammans med tre enkronor).
Nu kan man dock ha en invändning mot den sista punkten. Kan det inte vara smart att växla till sig en femma (om man redan har en), så att man i ett senare skede kan betala med två femmor istället för en femma och tre enkronor? Svaret på den frågan är nej. Det kostar oss tre extra mynt att växla till oss en femma. Skillnaden mellan två femmor och en femma tillsammans med tre enkronor är bara två, så vi förlorar faktiskt på den handlingen. Ponera t.ex. att vi ska köpa 3 burkar och har 1 tia, 3 femmor och 7 enkronor; då är det inte smart att växla till sig en femma (och inte i någon annan liknande situation heller).
Ja med detta i åtanke, så blir programmet inte särskilt svårt att konstruera.
import java.util.*;
public class Colaautomat
{
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal burkar: ");
int burkar = scan.nextInt();
System.out.print("Antal 1-kronor: ");
int enkronor = scan.nextInt();
System.out.print("Antal 5-kronor: ");
int femkronor = scan.nextInt();
System.out.print("Antal 10-kronor: ");
int tiokronor = scan.nextInt();
//Hur många colaburkar vi har köpt.
int cola = 0;
//Hur många mynt vi har använt.
int antal = 0;
//Köper burkar tills vi har uppnåt målet.
while(cola<burkar)
{
//Bör vi vara giriga? (Går det att komma fram till målet med bara tior och femmor?)
//Dvs bör vi bara försöka använda tior och två femmor i så
// stor utsträckning som möjligt.
boolean greedy = (burkar-cola)-tiokronor-femkronor/2<=0;
//Om vi har några tior.
if(tiokronor>0)
{
//Bör vi försöka växla till oss en femma genom att
// stoppa in en tia och tre enkronor? Vilket vi bör
// om vi inte kan nå fram till målet genom att använda
// de tior och femmor (tillsammans med 3 enkronor) som
// vi redan har.
boolean kr13 = (burkar-cola)-tiokronor-femkronor>0;
//Om vi inte ska vara giriga, och vi kan och bör växla till oss en femma.
if(!greedy && enkronor>=3 && kr13)
{
//Vi har använt fyra mynt.
antal += 4;
//Vi har fått en cola.
cola++;
//Vi använde tre enkronor.
enkronor -= 3;
//En tia.
tiokronor--;
//Och fick en femma i växel.
femkronor++;
}
else //Annars stoppar vi bara in en vanlig tia.
{
antal++;
cola++;
tiokronor--;
enkronor += 2;
}
}
else if(femkronor>0) //Om vi har några femmor.
{
//Om vi inte ska vara giriga och har tre enkronor.
if(!greedy && enkronor>=3)
{
//Då stoppar vi in en femma och tre enkronor.
antal += 4;
cola++;
femkronor--;
enkronor -= 3;
}
else //Annars stoppar vi bara in två femmor.
{
//Och ja vi kan vara säkra på att vi har två femmor.
//För om vi inte hade det, så skulle vi inte vara giriga
// och samtidigt ha nått denna position i koden.
antal += 2;
cola++;
femkronor -= 2;
enkronor += 2;
}
}
else //Har vi inga tior eller femmor, så har vi enkronor.
{
antal += 8;
cola++;
enkronor -= 8;
}
}
//Skriver ut svaret.
System.out.println("\nDu behöver stoppa in " + antal + " mynt.");
}
}
Dock kan det kanske inte vara så lätt att lista ut ovanstående. Och även om man har gjort det, så känner man nog sig inte särskilt trygg med sin lösning, såvida man inte testat den för diverse testfall. Och som programmerare föredrar man ju ofta helt enkelt att bara testa alla (vettiga) kombinationer, för det är något man gjort många gånger och känner sig trygg med. Så därför följer även en sådan lösning i Java här nedan.
För att få programmet tillräckligt snabbt måste man dock tänka lite på i vilken ordning man placerar testerna av de olika "vägvalen" och dessutom bör man markera/spara minsta antalet mynt som krävts för att uppnå ett visst antal burkar med en viss uppsättning mynt. Och till skillnad från den högst tveksamma lösningen i C++ ovan, så konstruerar vi "matrisen" med storleken [burkar+1][141][31][11] eftersom om man börjar med 100 enkronor och sedan stoppar i en tia (så att man får 2 enkronor i växel) ja då kommer man få exekveringsfel om man bara satt storleken till [41][101][21][11].
import java.util.*;
public class Colaautomat2
{
//Minsta antalet mynt som krävs.
static int min = Integer.MAX_VALUE;
//Fyrdimensionell matris för att markera positioner.
//[i][][][] antalet burkar.
//[][i][][] antalet enkronor.
//[][][i][] antalet femkronor.
//[][][][i] antalet tiokronor.
static int [][][][] chart;
//Rekursiv metod för att testa alla vettiga kombinationer av köp.
public static void rek(int mynt, int burkar, int tioKr, int femKr, int enKr)
{
//Onödigt att fortsätta.
if(mynt>=min) return;
//Vi är klara.
if(burkar==0)
{
min = mynt;
return;
}
//Om vi uppnått denna position tidigare.
if(chart[burkar][enKr][femKr][tioKr]!=0)
{
//Om vi redan har uppnått detta antal burkar
// med färre mynt för samma antal enkronor,
// femkronor och tiokronor, så bör vi avbryta.
if(mynt>=chart[burkar][enKr][femKr][tioKr]) return;
}
//Markerar positionen som besökt.
chart[burkar][enKr][femKr][tioKr] = mynt;
//Köper en burk med bara en tia.
if(tioKr>0) rek(mynt+1, burkar-1, tioKr-1, femKr, enKr+2);
//Köper en burk med en tia och tre enkronor.
if(tioKr>0 && enKr>=3) rek(mynt+4, burkar-1, tioKr-1, femKr+1, enKr-3);
//Köper en burk med en femma och tre enkronor.
if(femKr>0 && enKr>=3) rek(mynt+4, burkar-1, tioKr, femKr-1, enKr-3);
//Köper en burk med två femmor.
if(femKr>=2) rek(mynt+2, burkar-1, tioKr, femKr-2, enKr+2);
//Köper en burk med åtta enkronor.
if(enKr>=8) rek(mynt+8, burkar-1, tioKr, femKr, enKr-8);
}
public static void main(String [] klein)
{
Scanner scan = new Scanner(System.in);
System.out.print("Antal burkar: ");
int burkar = scan.nextInt();
System.out.print("Antal 1-kronor: ");
int enkronor = scan.nextInt();
System.out.print("Antal 5-kronor: ");
int femkronor = scan.nextInt();
System.out.print("Antal 10-kronor: ");
int tiokronor = scan.nextInt();
//Skapar vår "karta" för dynamisk programmering.
//Man kan max uppnå 140 enkronor, 30 femkronor och 10 tiokronor.
chart = new int [burkar+1][141][31][11];
//Dags att finna svaret,
//Vi har använt 0 mynt och har dessa startvärden.
rek(0, burkar, tiokronor, femkronor, enkronor);
//Skriver ut svaret.
System.out.println("\nDu behöver stoppa in " + min + " mynt.");
}
}