Tävlingsprogrammering/Uppgifter/Gravplundring
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)