Tävlingsprogrammering/Uppgifter/Köpa potatis

Köpa potatis

När man köper potatis är det ofta inte så viktigt hur stora potatisarna är, däremot är det smidigt om de är ungefär jämnstora så att man kan koka dem lika länge. Edward har uppmärksammat det här problemet och funnit en lösning som kan verka lite opraktisk. När han ska köpa potatis väger han först varje potatis som finns tillgänglig i affären. Därefter väljer han ut potatisar så att

de totalt väger minst V gram
viktskillnaden mellan den tyngsta och lättaste potatisen är så liten som möjligt.

Skriv ett program som hjälper Edward att räkna ut den minsta möjliga viktskillnaden.

På första raden i filen potatis.dat står två heltal separerade med blanksteg: antal tillgängliga potatisar (1 ≤ N ≤ 1000) och den minsta acceptabla totalvikten (1 ≤ V ≤ 10000) i gram. Därefter följer N rader med ett heltal på varje rad, vikten för varje potatis (mellan 1 och 1000 gram). Summan av alla vikterna är minst V , så det finns alltid en lösning. Programmet ska skriva ut den minsta möjliga skillnaden i vikt mellan den tyngsta och lättaste potatisen i ett optimalt urval av potatisar som totalt väger minst V gram.

Exempel: Filen potatis.dat med innehållet

ska ge svaret

Minsta skillnad: 151

Lösning

Här gäller det att inse att Edward alltid ska plocka en sammanhängande serie av potatisar i viktordning; det kan aldrig vara en fördel att hoppa över en potatis. Uppgiften blir därför enklast att lösa om man börjar med att sortera potatisarna. Sortering finns inbyggd i de flesta språk och har komplexiteten O(N log N).

Sedan kan man exempelvis loopa igenom alla potatisar och för varje potatis kolla hur långt fram i den ordnade serien man måste gå innan minimivikten uppnås om denna potatis väljs som den lättaste. Med tusen potatisar har man råd att göra en O(N²)-lösning, men det går också att göra en O(N)-lösning som uppdaterar störstavikten parallellt med minstavikten och därför bara går igenom potatisarna en gång (se exemplet).

Lösningsexempel i C/C++:

#include <stdio.h>
#include <algorithm>
using namespace std;

int main(){
  int N,V,v[1000],i,j,sum,m;
  FILE *fil=fopen("potatis.dat","rt");
  fscanf(fil, "%d %d", &N,&V);
  for(i=0;i<N;i++) fscanf(fil, "%d", &v[i]);
  sort(v,v+N);   //Sortera potatisarna efter vikt
  m=100000000;
  j=0;
  sum=v[0];
  for(i=0;i<N;i++) {    //Loopa över viktintervallets startpunkt
    while ((j<N-1) && (sum<V)) {     //Flytta vid behov fram slutpunkten 
      j++;
      sum+=v[j];    //Öka summan med nytillkomna potatisar
    }
    if(sum>=V) m=min(m,v[j]-v[i]);   //Uppdatera minsta skillnaden
    sum-=v[i];   //Minska summan när startpotatisen försvinner från intervallet
  }
  printf("Minsta skillnad: %d\n", m);
  return 0;
}

Här är ett lösningsexempel i Java med kvadratisk tidskomplexitet. Importerar java.io gör man för att få tillgång till klassen File. Vi ska ju läsa filen potatis.dat som (i det här exemplet) ligger i mappen data.

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

public class Potatis
{
	//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 potatis.dat i mappen/katalogen data.
		Scanner scan = new Scanner(new File("data\\potatis.dat"));

		//Antalet potatisar.
		int nr = scan.nextInt();

		//Obligatorisk vikt.
		int required = scan.nextInt();

		//Array där vi sparar potatisarna.
		int [] potatis = new int [nr];

		//Läser in alla potatisar.
		for(int i = 0; i<nr; i++)
		{
			potatis[i] = scan.nextInt();
		}

		//Minsta möjliga skillnaden.
		//Integer.MAX_VALUE är ett säkert val som startvärde.
		int min = Integer.MAX_VALUE;

		//Sorterar potatisarna. (I stigande ordning.)
		Arrays.sort(potatis);

		//Vikt vi har för tillfället.
		int current = 0;

		//Vår startposition.
		for(int i = 0; i<nr; i++)
		{
			//Vi vandrar från startpositionen och framåt.
			for(int j = i; j<nr; j++)
			{
				//Lägger till en potatis.
				current += potatis[j];

				//Om vi har uppnåt obligatorisk vikt.
				if(current>=required)
				{
					//Skillnaden mellan största och minsta i denna serie.
					int thisMin = potatis[j]-potatis[i];

					//Om den är mindre än den tidigare minsta är den minst.
					if(thisMin<min) min = thisMin;

					//Avbryter loopen.
					break;
				}
			}

			//Nollställer vikt. Nu ska vi hitta en ny serie.
			current = 0;
		}

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

Lösning i Haskell.

-- Potatisar
module Main where
import IO
import Data.List

main = do {
	ih <- openFile "potatis.dat" ReadMode;
		
	content <- hGetContents ih;
	
	stuff <- return $ map read $ tail $ words content;
	vikt <- return $ head stuff;
	
	putStrLn $ "Minsta skillnad: " ++ (show $ potatis vikt (sort $ tail stuff));
	
	hClose(ih)
}

potatis :: Int -> [Int] -> Int
potatis _ [] = 10000
potatis vikt pot@(h:t) =  min (loop vikt pot - h) (potatis vikt t)
	where
	loop _ [] = 10000
	loop v (h:t) = if (v - h <= 0) then h else loop (v-h) t

Man kan skriva oläsliga lösningar med få antal rader i Java också:

public class Potatis {
    public static void main(String[] args) {
        java.util.Scanner sc = new java.util.Scanner(System.in);
        for (int ps[] = new int[sc.nextInt() + 1], m = 1000000, v = sc.nextInt(), a = 0, b = 0, aw = 0, bw = 0, s = 0, i = 0; a != ps.length - 2; ps[Math.min(i++, ps.length - 1)] = i >= ps.length ? 0 : sc.nextInt(), java.util.Arrays.sort(ps, 0, i == ps.length ? ps.length : 0), System.out.print(i >= ps.length ? ((((s = s + (s < v && b != ps.length ? ps[b + (bw = ps[b]) * 0 + b++ * 0] : -ps[a + (aw = ps[a + 1]) * 0 + a++ * 0])) >= v && (m = Math.min(bw - aw, m)) > 0) + "").substring(0, 0) + ((a == ps.length - 1) ? (m + "\n") : "")) : ""));
    }
}