Tävlingsprogrammering/Uppgifter/Gravplundring

Från Wikibooks

Gravplundring (PO-kvalet 2008)


Gravplundraren Rolf har hittat en bortglömd faraonisk grav som han tänker plundra. I graven finns en mängd föremål med varierande vikt och av varierande värde. Rolf vill naturligtvis få med sig en samling med så stort värde som möjligt. Kruxet är bara att han endast har två dromedarer att lasta skatterna på. Varje dromedar kan bära högst 150 kilo. Skriv ett program som, givet vikten och värdet för varje föremål, bestämmer det maximala värdet Rolf kan forsla bort på de två dromedarerna. Inget av föremålen går att dela upp mellan de två djuren.

Programmet ska fråga efter antalet föremål N (där 1 ≤ N ≤ 14), samt vikten M och värdet V för varje föremål. Både M och V är heltal och uppfyller 1 ≤ M ≤ 150, 1 ≤ V ≤ 1000. Programmet ska skriva ut det maximala sammanlagda värdet av de föremål som Rolf kan lasta på de två dromedarerna.

Körningsexempel:

Antal föremål ? 3 
Föremål 1, vikt ? 70 
Föremål 1, värde ? 180 
Föremål 2, vikt ? 90 
Föremål 2, värde ? 150 
Föremål 3, vikt ? 100 
Föremål 3, värde ? 200  
Maximalt totalvärde: 380 

Lösning[redigera]

Om det bara funnits en dromedar hade detta varit ett standardproblem inom algoritmteori, nämligen knapsack-problemet. Det problemet kan (förutsatt att föremålens vikter är heltal) lösas effektivt med hjälp av dynamisk programmering. Man har en vektor där man för varje vikt V sparar det högsta möjliga värdet av föremål som tillsammans väger V kg (eller t.ex. -1 om det inte går att få exakt V). Från början är 0 den enda möjliga vikten. Man går igenom varje föremål i tur och ordning. För varje föremål (med vikten Vi) uppdaterar man vektorn genom att för varje möjlig tidigare uppnådd vikt V kolla om man med hjälp av det aktuella föremålet kan uppnå ett värde som är högre än det tidigare maxvärdet för vikten V+Vi.

Nu är det dock två dromedarer vilket krånglar till det lite. Man får ersätta vektorn med en två-dimensionell matris där man för varje par av vikter V1 och V2 sparar det högsta möjliga värdet av föremål som kan lastas så att den ena dromedaren bär V1 kg och den andra V2 kg. För varje föremål i går man igenom hela matrisen och för varje tidigare uppnått par av vikter (V1, V2) kollar man om man kan färbättra värdet för viktparen (V1+Vi, V2) eller (V1, V2+Vi). När alla föremål behandlats är svaret helt enkelt det maximala värdet någonstans i matrisen (djuren behöver inte lastas med exakt 150 kg).

För sådana dynamiska lösningar är tidsåtgången proportionell mot N*Mk, där N är antalet föremål, M är dromedarens lastvikt och k är antalet dromedarer. Med två dromedarer och lastvikten 150 kan man sålunda hantera 100 föremål utan problem. I denna uppgift är det dock max 14 föremål, vilket gör att man faktiskt kan göra en brute force-lösning som urskiljningslöst testar alla möjliga sätt att lasta föremålen (314=4782969 stycken).

Lösningsexempel i C

#include <stdio.h> 
#define M 150
int MAX(int p, int q) { return (p>q)?p:q; }

int T[M+1][M+1];

int main(){
  int N,i,j,k,wt[20],val[20],max;
  printf("Antal föremål ? ");
  scanf("%d", &N);
  for(i=0;i<N;i++) {
    printf("Föremål %d, vikt ? ",i+1);
    scanf("%d", &wt[i]);
    printf("Föremål %d, värde ? ",i+1);
    scanf("%d", &val[i]);
  }
  for(i=0;i<=M;i++) for(j=0;j<=M;j++) T[i][j]=-1; //Markera alla viktpar som ouppnådda...
  T[0][0]=0;                                       // .... utom (0,0)
  for(i=0;i<N;i++) {   //Loopa över föremålen
    for(j=M;j>=0;j--) for(k=M;k>=0;k--) if(T[j][k]!=-1) { //Loopa över alla uppnådda viktpar
      if(j+wt[i]<=M) T[j+wt[i]][k] = MAX(T[j+wt[i]][k], T[j][k]+val[i]); //Testa lastning på dromedar 1 och uppdatera matrisen om bättre lösning hittas
      if(k+wt[i]<=M) T[j][k+wt[i]] = MAX(T[j][k+wt[i]], T[j][k]+val[i]); //Testa lastning på dromedar 2 och uppdatera matrisen om bättre lösning hittas
    }
  }
  max=0;
  for(j=0;j<=M;j++) for(k=0;k<=M;k++) max = MAX(max,T[j][k]); //Ta fram det maximala värdet i matrisen
  printf("Maximalt totalvärde: %d\n", max);
  return 0;
}

Ett bidrag från en användare. Det visar hur man kan lösa denna uppgift med brute force metoden istället. Programmet använder en rekursiv plundra() som anropar sig själv tills den får fram en hel rad med 0, 1, eller 2:or. Exempelvis med 4 föremål kan en rad se ut 0012 och det innebär att de två första föremålen inte kommer användas och det 3:e av dromedar 1 osv. Jag fixade även en debugger så man kan se vad som händer bakom kulisserna. Programmet är skrivet i C++.

#include <cstdlib>
#include <iostream>

using namespace std;

int arr[15];
int weight[15];
int value[15];
int antal;
int maxprice=0;
int debug=0;

int plundra(int N) {
   int i;
   int p1=0, p2=0;
   int w1=0, w2=0;
   if (N==antal) {  // Om vi är i slutet av en rad
       if (debug==1) {
           for (i=0; i<antal; i++) cout << arr[i];
           cout << "   ";
       }
       for (i=0; i<antal; i++) {   // Loopa igenom raden
           if (arr[i] == 1) {      // Lägg till dromedar 1 och testa vikt
               w1 += weight[i];
               if (w1 > 150) {
                   if (debug==1) cout << "Too much: " << w1 << endl; 
                   return 0;
               }
               p1 += value[i];     // Annars öka värdet på dromedar 1
           }
           else if (arr[i] == 2) { // Gör samma sak med dromedar 2
               w2 += weight[i];
               if (w2 > 150) {
                   if (debug==1) cout << "Too much: " << w2 << endl; 
                   return 0;
               }
               p2 += value[i];
           }     
       }
       if (p1 + p2 > maxprice) {   // Om värdet tillsammans är större än tidigare värden
           if (debug == 2) {
               for (i=0; i<antal; i++) cout << arr[i];
               cout << "   ";
           }
           maxprice = p1 + p2;     // Tilldela värdet till maxprice
           if (debug) cout << "Max found: " << maxprice << endl;
           return 0;
       }
       if (debug==1) cout << endl;
       return 0;
   }
   else {
       for (i=0; i<3; i++) {      // Testa med 0, 1 och 2
           arr[N] = i;
           plundra(N+1);       // Gå till nästa
       }
   }
   return 0; 
}
int main(int argc, char *argv[]) {
   int i;
   cout << "Debug (0=Off, 1=All, 2=MaxPrice) ? ";
   cin >> debug;
   cout << "Antal ? ";  // Läs in allt
   cin >> antal;
   for (i=0; i<antal; i++) {
       cout << "Föremål " << (i+1) << ", vikt ? ";
       cin >> weight[i];
       cout << "Föremål " << (i+1) << ", värde ? ";
       cin >> value[i];
   }
   plundra(0);  // Starta den rekursiva funktionen
   cout << "Maximalt totalvärde: " << maxprice << endl;
   return 0;
}

Ett lösningsexempel i Java som använder sig av brute force, d.v.s. prövar alla kombinationer och kollar vilken som är bäst.

import java.util.*;

public class Dromedarer
{
	//Föremålens vikt.
	static int [] vikt;

	//Föremålens värde.
	static int [] varde;

	//Maxvärde för dromedar 1 och 2.
	static int max1, max2;

	//Antal föremål.
	static int N;

	//Vår rekursiva metod som löser problemet.
	/*
	value1: Värdet av föremålen som dromedar 1 har på sig.
	value2: Värdet av föremålen som dromedar 2 har på sig.
	weight1: Vikten av föremålen som dromedar 1 har på sig.
	weight2: Vikten av föremålen som dromedar 2 har på sig.
	i: Indexet för det föremål som vi för stunden ska testa att lasta.
	*/
	public static void rek(int value1, int value2, int weight1, int weight2, int i)
	{
		//Vi har tagit oss vatten över huvudet, dvs lastat för mycket.
		if(weight1>150 || weight2>150) return;

		//Om denna kombination är bättre än den "nuvarande" bästa.
		if(value1+value2>max1+max2)
		{
			max1 = value1;
			max2 = value2;
		}

		//Vi kör på så länge det finns föremål kvar att testa.
		if(i<N)
		{
			rek(value1+varde[i], value2, weight1+vikt[i], weight2, i+1); //Lastar första dromedaren.

			rek(value1, value2+varde[i], weight1, weight2+vikt[i], i+1); //Lastar andra dromedaren.

			rek(value1, value2, weight1, weight2, i+1); //Lastar ingen (kan ju vara ett "dåligt" föremål).
		}
		else //Behövs egentligen inte, men symboliserar att vi är klara när alla föremål är avverkade.
		{
			return;
		}
	}

	public static void main(String [] klein)
	{
		Scanner scan = new Scanner(System.in);

		System.out.print("Antal föremål: ");
		N = scan.nextInt();

		vikt = new int [N];
		varde = new int [N];

		for(int i = 0; i<N; i++)
		{
			System.out.print("Föremål "+(i+1)+" vikt: ");
			vikt[i] = scan.nextInt();

			System.out.print("Föremål "+(i+1)+" värde: ");
			varde[i] = scan.nextInt();
		}

		//Nu ska vi finna svaret.
		//Vi börjar enligt logikens alla lagar med 0 på alla punkter eftersom ingen av dromedarerna har något föremål
		// på sig och följaktligen inget av vikt eller värde på sig.
		//Sedan så ska vi ju börja med att testa att lasta det första föremålet och det har index 0.
		rek(0, 0, 0, 0, 0);

		System.out.println("\nMaximalt värde: " + (max1+max2));
	}
}

Lösning i Haskell.

-- Gravplundring
module Main where
import IO

main = do {
	putStr "Antal foremal: ";
	antal <- getLine;
	
	items <- readItems 1 (read antal);
	
	putStrLn ("Maximalt totalvarde: " ++ (show $ bruteForce items))
}

readItems :: Int -> Int -> IO [(Int,Int)]
readItems _ 0 = return []
readItems n to = do {
		putStr ("Foremal " ++ (show n) ++ ", vikt ? ");
		vikt <- getLine;
		
		putStr ("Foremal " ++ (show n) ++ ", varde ? ");
		value <- getLine;
		
		rest <- readItems (n+1) (to-1);
		
		return $ (read vikt, read value):rest
}

bruteForce :: [(Int, Int)] -> Int
bruteForce items = loop items (0,0) (0,0)
	where
	loop [] (a1,b1) (a2,b2) = if (a1>150 || a2>150) then 0 else b1+b2
	loop (h:t) (a,b) (c,d) 	| a>150 || c>150	= 0
				| otherwise		= maximum [branch1, branch2, branch3]
				where
				branch1 = loop t (fst h + a, snd h + b) (c,d)
				branch2 = loop t (a,b) (fst h + c, snd h + d)
				branch3 = loop t (a,b) (c,d)