Tävlingsprogrammering/Uppgifter/Köpa böcker

Köpa böcker

Du ska köpa N böcker av olika slag (numrerade från 1 till N) och kollar därför runt hos internetbokhandlarna. Varje bok ﬁnns hos minst en bokhandel och kan variera i pris mellan de olika bokhandlarna. Dessutom kostar det ett visst belopp i porto att beställa från varje bokhandel, oavsett hur mycket man beställer. Skriv ett program som beräknar det minimala beloppet böckerna kostar dig, inräknat porto. Du kan beställa från hur många bokhandlar som helst.

Indata

Första raden i ﬁlen bok.dat innehåller två tal: N, antalet böcker du ska köpa (1 ≤ N ≤ 100), och M, antalet bokhandlar (1 ≤ M ≤ 15). Därefter följer en rad med två tal som anger antalet böcker K (av de eftersökta) som ﬁnns i första bokhandeln, samt portot för denna bokhandel. Detta följs av K rader innehållande två tal: numret på en bok som ﬁnns i bokhandeln och dess pris. Denna information upprepas sedan för återstående bokhandlar. Alla priser och porton anges i hela kronor och överstiger inte 10, 000.

Utdata

Programmet ska skriva ut det minimala beloppet böckerna kostar, inräknat portokost- naden för alla bokhandlar du beställer från.

Körningsexempel: Indata

Körningsexempel: Utdata

Lösning

Det vi måste inse är att vi inte bör köra: För varje bok, testa att köpa den av olika bokhandlar. Utan istället att vi måste testa alla olika fall av vilka bokhandlar vi köper ifrån, och vilka vi inte köper ifrån. Sedan är det bara att kolla upp, för varje bok, var den är billigast. Vi måste även hålla koll på om boken inte fanns i någon bokhandel, utifrån de vi har valt att kolla i. Eftersom vi endast har 15 bokhandlar, blir det endast som mest 2^15=32768 olika fall av vilka bokhandlar man väljer, så 5-sekundersgränsen ligger inom stor marginal.

Här är ett lösningsförslag i C++, som använder en rekursiv funktion för att välja bokhandlar man köper ifrån. Det går naturligtvis att använda sig av loopar eller något annat om man hellre vill det.

#include <iostream>
#include <fstream>
using namespace std;

int N, M, K[15], porto[15], pris_bok[15][100];
bool finns_i_handel[15][100];
int billigast;
bool billigast_finns = false; //Om vi ännu har hittat ett pris överhuvudtaget
bool handel_vald[15];

void rek(int antal_bokhandlar_kollade, int pris){ //pris innehåller bara totala portot, fram tills man ska se var respektive bok är billigast
	if (antal_bokhandlar_kollade == M){
		//Vi har nu valt vilka bokhandlar vi har valt att köpa ifrån, kolla nu för varje bok var den är billigast
		for(int i=0; i<N; i++){
			bool hittad = false;
			int billigast_pris;
			for(int j=0; j<M; j++) if (handel_vald[j] && finns_i_handel[j][i]) {
				if (!hittad || billigast_pris > pris_bok[j][i]){
					//Av de handlar hittills testade, så är den billigast här
					hittad = true;
					billigast_pris = pris_bok[j][i];
				}
			}
			if (!hittad) return; //Boken fanns inte i någon av de valda bokhandlarna
			pris += billigast_pris;
		}
		if (!billigast_finns || billigast > pris){
			//Vi har hittat ett nytt billigast totalpris
			billigast_finns = true;
			billigast = pris;
		}
	} else {
		//Testa att köpa från denna bokhandel
		handel_vald[antal_bokhandlar_kollade] = true;
		rek(antal_bokhandlar_kollade+1, pris+porto[antal_bokhandlar_kollade]);
		
		//Testa att inte köpa från denna bokhandel
		handel_vald[antal_bokhandlar_kollade] = false;
		rek(antal_bokhandlar_kollade+1, pris);
	}
}

int main(int argc, char *argv[]){
	for(int i=0; i<15; i++) for(int j=0; j<100; j++) finns_i_handel[i][j] = false;
	
	ifstream fil("bok.dat");
	
	//Parse:a indata
	fil >> N >> M;
	for(int i=0; i<M; i++){
		fil >> K[i] >> porto[i];
		for(int j=0; j<K[i]; j++){
			int bok_nr, pris;
			fil >> bok_nr >> pris;
			finns_i_handel[i][bok_nr-1] = true;
			pris_bok[i][bok_nr-1] = pris;
		}
	}
	
	//Kör vår rekursiva funktion
	rek(0, 0);
	
	//Skriv ut vad lägsta priset blir
	cout << billigast << endl;
	
	fil.close();
	return 0;
}

Liknande lösning, fast i Java.

import java.util.*;
import java.io.*;

public class BuyBooks
{
	//Lagrar priset för en viss bok hos en bokhandlare.
	//-1 om boken inte finns.
	static int [][] store;

	//Lagrar portot för en viss bokhandlare.
	static int [] porto;

	//Minsta kostnaden.
	static int min = 2000000;

	//Antalet böcker och bokhandlare.
	static int N, M;

	//Rekurivs metod för att välja de bokhandlare vi ska köpa från.
	//shop: Bokhandlaren vi ska avverka.
	//shops: Bokhandlarna vi hittills har valt att köpa från.
	public static void rek(int shop, LinkedList <Integer> shops)
	{
		//Nu har vi avverkat alla bokhandlare och kan beräkna den
		//billigaste kostnaden för att köpa alla böcker med denna
		//uppsättning bokhandlare.
		if(shop==M)
		{
			goGreedy(shops);
			return;
		}

		//Vi väljer att handla från denna bokhandlare.
		shops.addLast(shop);
		rek(shop+1, shops);

		//Vi väljer att inte handla från denna bokhandlare.
		shops.removeLast();
		rek(shop+1, shops);
	}

	//Beräknar minsta möjliga kostnaden om vi ska köpa böcker från
	//alla de bokhandlare som anges i shops.
	public static void goGreedy(LinkedList <Integer> shops)
	{
		//Kostnaden vi kommit upp i.
		int cost = 0;

		//Eftersom vi ska handla från alla, så betalar vi alla
		//porton med en gång.
		for(int shop : shops) cost += porto[shop];

		//Går igenom varje bok och hittar det billigaste alternativet.
		for(int i = 1; i<=N; i++)
		{
			//Ingen bok kostar mer än 10000.
			int best = 11000;

			//Kollar hos de bokhandlare vi ska köpa från.
			for(int shop : shops)
			{
				//Om boken finns och är billigare än tidigare billigaste.
				if(store[i][shop]!=-1 && store[i][shop]<best)
				{
					//Ja då är detta vår hittills billigaste.
					best = store[i][shop];
				}
			}

			//Om den bästa kostnaden är skild från 11000, så fanns boken
			//och vi ökar på kostnaden med det bästa valet.
			if(best<11000) cost += best;
			else return; //Annars om boken inte fanns, så kan vi avbryta.
		}

		//Kollar om denna kostnad var bättre än tidigare bästa.
		if(cost<min) min = cost;
	}

	//Orka fånga exceptions. Vi är lata och säkra på vår sak.
	public static void main(String [] klein) throws FileNotFoundException
	{
		//Vi ska läsa av filen bok.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\bok.dat"));

		//Läser in antalet böcker.
		N = scan.nextInt();

		//Läser in antalet bokhandlare.
		M = scan.nextInt();

		//Skapar bokhandlarna.
		store = new int [N+1][M];

		//Markerar alla böcker till en början med -1.
		//(Vilket betyder att boken inte finns.)
		for(int i = 0; i<M; i++)
			for(int j = 1; j<=N; j++)
				store[j][i] = -1;

		//Sparar portot för en viss butik.
		porto = new int [M];

		//Läser in alla böcker för varje bokhandalre.
		for(int i = 0; i<M; i++)
		{
			//Hur många böcker denna handlare har.
			int K = scan.nextInt();

			//Läser in portot för bokhandlaren.
			porto[i] = scan.nextInt();

			//Läser in priset för de böcker som finns hos denna handlare.
			for(int j = 0; j<K; j++)
			{
				store[scan.nextInt()][i] = scan.nextInt();
			}
		}

		//Vi finner svaret.
		rek(0, new LinkedList <Integer> ());

		//Skriver ut svaret.
		System.out.println("Minsta kostnad: " + min);
	}
}