Tävlingsprogrammering/Uppgifter/Bokhyllor

Bokhyllor

Du ska köpa bokhyllor för att få plats med alla dina böcker. Du vet från början vilka böcker du har och behöver räkna ut antalet bokhyllor som krävs. Böckerna har tre olika storlekar: en liten bok tar 1 platsenhet, en mellanstor 2 och en stor bok tar 3 platsenheter. Varje hylla rymmer ett visst antal platsenheter. Givet hur många böcker du har av varje sort, skriv ett program som beräknar hur många hyllor du behöver om du vill ha så få hyllor som möjligt. Antalet böcker av varje sort kommer vara högst 20.

Körningsexempel 1

Antal små ? 30
Antal mellan ? 0
Antal stora ? 0
Hyllstorlek ? 10
Antal hyllor: 3

Du sätter 10 små böcker på varje hylla.

Körningsexempel 2

Antal små ? 0
Antal mellan ? 0
Antal stora ? 10
Hyllstorlek ? 10
Antal hyllor: 4

Du sätter 3 stora böcker på 3 hyllor, och får tyvärr en hylla till med bara en bok i.

Körningsexempel 3

Antal små ? 8
Antal mellan ? 7
Antal stora ? 5
Hyllstorlek ? 15
Antal hyllor: 3

Körningsexempel 4

Antal små ? 1
Antal mellan ? 4
Antal stora ? 13
Hyllstorlek ? 7
Antal hyllor: 8

Lösning

Problemet blir enklare om man inser några fakta:

• Om du har tvåor kvar och det finns plats för en tvåa är det alltid bättre att sätta en tvåa än två ettor.
• Om du har ettor kvar och det finns plats för en etta är det alltid bättre att sätta en etta än att lämna tomt.

Däremot är det inte lika självklart om man ska sätta en tvåa eller en trea när det finns plats för vilket som. Man kan klura ut fler regler men man måste nog ändå testa några olika sätt.

Problemet kan lösas genom att man testar varje möjligt antal treor på en hylla (minst en trea måste man ta om man har kvar, för någon gång måste de ju sättas in). För varje val proppar man in övriga böcker enligt reglerna ovan, och sedan står man inför samma problem igen fast med färre antal böcker. Detta är alltså perfekt för en rekursiv funktion som anropar sig själv.

Exempellösning i C:

#include <stdio.h>
int MIN(int p, int q) {return p<q?p:q;}

int N;

int antalhyllor(int n1, int n2, int n3) {   //Hur många hyllor behövs om vi har n1 ettor, n2 tvåor och n3 treor kvar? 
  int best=100000, i3,i2,i1,g1,g2;
  if(n1==0 && n2==0 && n3==0) return 0;   //För 0 böcker behövs 0 hyllor
  g1=(n3>0)?1:0;   //Minsta antalet treor att testa: 1 om vi har några kvar
  g2=MIN(n3,N/3);   //Största antalet treor att testa
  for(i3=g1;i3<=g2;i3++) {   //Loopa över antalet treor vi sätter in
    i2=MIN((N-i3*3)/2,n2);    //Kläm in så många tvåor det går
    i1=MIN(N-i3*3-i2*2,n1);   //Kläm in så många ettor det går
    best=MIN(best,1+antalhyllor(n1-i1,n2-i2,n3-i3));      //Rekursera. Om detta är det minsta antalet hittills så spara det i best
  }
  return best;
}

int main() {
  int ett,tva,tre;
  scanf("%d %d %d %d", &ett,&tva,&tre,&N);
  printf("%d\n",antalhyllor(ett,tva,tre));
  return 0;
}

Och som vi alla vet, är det Haskell som är kung på rekursiva funktioner.

-- Bokhyllor
module Main where

getInt = fmap read getLine :: IO Int
main = putStr "Antal sma ? " >> getInt >>= \low ->
	putStr "Antal mellan ? " >> getInt >>= \mid ->
	putStr "Antal stora ? " >> getInt >>= \big ->
	putStr "Hyllstorlek ? " >> getInt >>= \hylla ->
	putStrLn.("Antal hyllor: "++).show $ rek hylla low mid big

rek _ 0 0 0 = 0
rek n l m b = 1 + minimum [rek n (l-z) (m-y) (b-x) | x <- [s..min (div n 3) b], let (y,z) = (min m $ div (n-x*3) 2, min l $ n-x*3-y*2)]
	where s = if b>0 then 1 else 0