Tävlingsprogrammering/Uppgifter/Godisautomaten
Godisautomaten
Fil:Kommer-snart.png
FIGUR 4. Ett exempel på hur godisautomaten kan vara laddad. För att få tag i varorna A, C, F och D måste Herbert minst köpa de sex inringade varorna.
En viss godisautomat består av v ”våningar”, där varje våning består av en roterbar skiva. Varje våning är indelad i ett antal celler, där varje cell innehåller en vara. Figuren ovan visar hur det kan se ut. I automatens glas kan man se ett visst antal c av cellerna på varje våning, vi kan anta att övriga celler är tomma. Man kan köpa en vara från vilken våning som helst, men bara från den cell som för tillfället befinner sig längst till höger. När denna vara köpts roterar skivan så att den vara som fanns i cellen närmast till vänster om den köpta blir möjlig att köpa nästa gång.
Automaten kan innehålla upp till 26 olika sorters varor, var och en benämnd med en bokstav i intervallet A...Z. Varorna kan vara utspridda hur som helst.
Herbert har glömt äta lunch och skulle vilja köpa ett antal olika varor. Men för att lyckas med detta måste han troligtvis köpa en del andra varor som han inte alls har något behov av. Skriv ett program som, givet varornas placering i automaten, beräknar det minimala antalet oönskade varor Herbert måste köpa för att få tag på de varor han verkligen vill ha. Observera att om han måste köpa flera exemplar av de önskade varorna så räknas alla utom ett exemplar som oönskade varor.
Indata läses från filen godis.dat. På första raden står heltalen v, c och n, (1 ≤ c, v ≤ 100 och 1 ≤ n ≤ 12), där v är antalet våningar, c antalet synliga celler på varje våning och n är antalet varor som Herbert vill ha. Därefter följer v rader, vardera bestående av en sträng med c tecken i intervallet A...Z. Var och en av dessa rader beskriver en våning, och ordningen på bokstäverna beskriver innehållet i cellerna på denna våning, från vänster till höger. Slutligen följer en rad med n olika tecken i intervallet A...Z. Varje tecken är namnet på en vara som Herbert vill ha. Alla dessa varor finns i automaten.
Körningsexempel:
Filen godis.dat med innehållet: 5 6 4 ACBDEG CBEDHG CACDHE BFCHFA BGDAFB ACFD ska ge svaret: Antal onödiga varor: 2
Lösning
redigeraNyckeln till att lösa uppgiften är dynamisk programmering. Man håller reda på minsta antalet varor man behöver köpa för att uppnå en viss mängd godisar och går igenom automaten våning för våning. En viss uppsättning godisar kan lämpligen representeras med en bitmask, vilken kan i värsta fall anta värden mellan 0 och 2^12 - 1 (12 var övre gränsen för önskade varor). T.ex. om man vill ha varorna ADGHQ, kan 01011 (som är talet 11) representera att man har varorna D, H och Q.
Dock måste man vara uppmärksam på och ta hänsyn till följande fall. Säg att vi vill ha varorna EKRI. Betrakta följande två våningar.
REQJWIRK
BAEROKAI
Det bästa sättet att få varorna KRI = 0111 är uppenbarligen 3 (köpa de tre första ur den övre våningen), men det bästa sättet att få EKRI = 1111 är uppenbarligen 6 (köpa de sex första ur andra våningen), varför vi måste hålla reda på det senaste sättet att uppnå en viss konfiguration där man köpt varor på våningen man "befinner sig på". T.ex. måste vi spara att vi uppnådde KRI = 0111 med 5 köpta varor på våningen vi befann oss på, så att vi i nästa steg kan se att bara en ytterliggare vara behöver köpas och att detta sätt är bättre än om vi skulle köpa KRI ur den första våningen, d.v.s 5+6-5 (varor som krävts för att få KRI + varor som måste köpas för att få E - varor vi redan köpt på våningen för att få KRI) är bättre än 3+6 (minsta antalet varor som krävs för att få KRI + varor som måste köpas för att få E). Detta görs i lösningen nedan m.h.a. matrisen tmp.
Antalet onödiga varor är förstås det minsta antal varor som behöver köpas för att få varorna man vill ha - antalet varor man vill ha. I exemplet ovan behöver vi köpa 6 varor för att få EKRI = 1111 (= 2^4 - 1), så 6 - 4 = 2 blir antalet onödiga varor.
import java.util.*;
import java.io.*;
public class GodisAutomaten
{
public static void main(String [] klein) throws Exception
{
//Vi ska läsa av filen godis.dat.
Scanner scan = new Scanner(new File("godis.dat"));
//Antalet våningar, celler och önskade varor.
final int V = scan.nextInt(), C = scan.nextInt(), N = scan.nextInt();
//Läser in godisautomaten.
char [][] automat = new char [V][];
for(int i = 0; i<V; i++) automat[i] = scan.next().toCharArray();
//Vilka godisar vi vill ha.
char [] want = scan.next().toCharArray();
//Anger vilket index i bitmasken ett visst godis ska ha.
int [] val = new int [26];
for(int i = 0; i<26; i++) val[i] = -1; //-1 om godiset är oönskat.
for(int i = 0; i<N; i++) val[want[i]-'A'] = i; //Sitt index i strängen vi läste in annars.
// dp[0110] = minsta antalet varor man behöver köpa för att få godisarna
// med index 1 och 2.
int [] dp = new int [1<<N]; //Viktigt dock att dp[0] = 0.
for(int i = 1; i<1<<N; i++) dp[i] = 1337; //Initialiserar med ett stort tal > 1200.
//Går igenom varje våning i godisautomaten.
for(int i = 0; i<V; i++)
{
//Håller reda på vilka varor på våningen vi har köpt.
boolean [] bought = new boolean [26];
int [][] tmp = new int [2][1<<N]; //Obs: tmp[0][0] = 0.
for(int j = 1; j<dp.length; j++) tmp[0][j] = 1337;
//Går igenom varorna på våningen.
for(int j = C-1; j>=0; j--)
{
int vara = automat[i][j] - 'A';
int vidx = val[vara]; //Varans index.
//Om varan är en sådan vi vill ha och vi inte redan testat att köpa den på
// samma våning, så testar vi att köpa den.
if(vidx>=0 && !bought[vara])
for(int k = 0; k<dp.length; k++)
{
int bitmask = k|(1<<vidx); //Lägger till varan till mängden k.
if(k==bitmask) continue; //Varan är redan köpt, gå vidare.
//cost: Om vi bygger vidare på den för k globalt bästa.
//cost2: Om vi bygger vidare på den bästa som använt godis på våningen.
int cost = dp[k] + C-j, cost2 = tmp[0][k] + C-j - tmp[1][k];
//Sparar det minsta antal varor som behövs köpas för att uppnå konfiguationen
// som specificers av bitmask, där åtminstone en vara är köpt på nuvarande våning.
tmp[0][bitmask] = Math.min(cost,cost2);
tmp[1][bitmask] = C-j; //Antalet köpta godisar på våningen.
//Om det är bättre än det tidigare bästa, så spara!
if(tmp[0][bitmask]<dp[bitmask]) dp[bitmask] = tmp[0][bitmask];
}
//Nu har vi garanterat köpt den här varan.
bought[vara] = true;
}
}
//[Antalet onödiga varor] = [Minsta antalet varor som krävs att köpa för att
// få de varor vi vill ha] - [Antalet varor vi vill ha]. (1<<N) - 1 = N st ettor.
System.out.println("Antal onödiga varor: " + (dp[(1<<N)-1] - N));
}
}