Tävlingsprogrammering/Uppgifter/Bevattning

Bevattning (PO-kvalet 2008)

En bevattningskanal avledd från Nilen förser ett antal åkrar med vatten. Efter att i åratal ha trätit om hur mycket vatten varje åker ska få under torkperioden, beslutar sig bönderna för att samarbeta och istället minimera totalförlusten orsakad av torka.

För varje åker vet man följande:

• Den optimala volymen vatten (det är ingen idé att överskrida denna).
• Känsligheten, d.v.s. hur stor ekonomisk förlust som görs för varje volymenhet vatten under den optimala volymen.
• Den minimala volymen vatten för att åkern alls ska ge skörd.

Bönderna vill fördela vattnet så att den sammanlagda förlusten för alla åkrarna blir så liten som möjligt, samtidigt som varje åker ska ge åtminstone någon skörd. Skriv ett program som beräknar den minimala förlusten.

Programmet ska fråga efter den totala volymen tillgängligt vatten, antalet åkrar (högst 5), och sedan för varje åker efter optimala volymen, känsligheten och minimala volymen. Alla tal ligger i intervallet 1..1000. Programmet ska skriva ut den minimala sammanlagda förlusten. Vattnet kan endast fördelas i hela volymenheter. Allt vatten behöver inte nödvändigtvis användas. I samtliga testfall finns det tillräckligt mycket vatten för att varje åker ska ge skörd.

Körningsexempel:

Totalvolym ? 106  
Antal åkrar ? 2 
Åker 1, optimal volym ? 54 
Åker 1, känslighet ? 4 
Åker 1, minimal volym ? 41 
Åker 2, optimal volym ? 75 
Åker 2, känslighet ? 6 
Åker 2, minimal volym ? 56  
Minimal förlust: 112 

Kommentar: Den bästa fördelningen är 41 volymenheter till åker 1 och 65 volymenheter till åker 2. Detta ger en förlust på 13 * 4 + 10 * 6 = 112.

Lösning

Här gäller det att inse att om det finns för lite vatten för att alla åkrar ska få optimal volym, så ska man alltid minska vattenmängden så mycket som möjligt på de minst känsliga åkrarna först. Man kan därför beräkna det totala underskottet, sortera åkrarna i känslighetsordning och sedan gå igenom åkrarna var för sig och minska vattenmängden så mycket det går för varje åker till dess att underskottet är borta.

En sådan lösning, där man inte behöver testa alla kombinationer utan kan ta det alternativ som verkar bäst för stunden, brukar kallas för girig (greedy).

Lösningsförslag i C

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

int main(){
  int N,mi,ma,de,dec[20],cap[20],tot,i,j,k,c,loss;
  printf("Totalvolym ? ");
  scanf("%d", &tot);
  printf("Antal åkrar ? ");
  scanf("%d", &N);
  for(i=0;i<N;i++) {
    printf("Åker %d, optimal volym ? ",i+1);
    scanf("%d", &ma);
    printf("Åker %d, känslighet    ? ",i+1);
    scanf("%d", &de);
    printf("Åker %d, minimal volym ? ",i+1);
    scanf("%d", &mi);
    //Spara värdena sorterat efter känsligheten
    for(j=0;j<i;j++) if (de<dec[j]) {  //Hitta rätt plats
      for(k=i-1;k>=j;k--) { //Flytta undan efterföljande element
        dec[k+1]=dec[k];
        cap[k+1]=cap[k];
      }
      break;
    }
    dec[j]=de;
    cap[j]=ma-mi; //Spara hur stor volym vi maximalt kan undvara på åkern 
    tot-=ma; //Hur stort överskott har vi? (oftast negativt)
  }
  loss=0;
  for(i=0;(i<N) && (tot<0);i++) {    //Så länge vi har underskott, gå igenom åkrarna med början på de minst känsliga
    c=MIN(-tot,cap[i]); //Ta bort det maximala vi kan undvara på åkern (men inte mer än underskottet)
    loss+=dec[i]*c;    //Hur mycket kostar detta?
    tot+=c;            //Uppdatera underskottet
  }
  printf("Minimal förlust: %d\n",loss);
  return 0;
}

Lösningsexempel i Java.

import java.util.*;

public class Bevattning
{
	//Retunerar indexet för den mest känsliga åkern.
	public static int findMostSensitive(int [] sens)
	{
		int max = sens[0];
		int index = 0;

		for(int i = 1; i<sens.length; i++)
		{
			if(sens[i]>max)
			{
				max = sens[i];
				index = i;
			}
		}

		return index;
	}

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

		System.out.print("Total volym: ");
		int volym = scan.nextInt();

		System.out.print("Antal åkrar: ");
		int antal = scan.nextInt();

		//Skapar åkern.
		int [][] aker = new int [3][antal];

		//Hur mycket volym vatten en viss åker fått.
		int [] current = new int [antal];

		for(int i = 0; i<antal; i++)
		{
			System.out.print("Åker " + (i+1) + ", optimal volym: ");
			aker[0][i] = scan.nextInt();

			System.out.print("Åker " + (i+1) + ", känslighet: ");
			aker[1][i] = scan.nextInt();

			System.out.print("Åker " + (i+1) + ", minimal volym: ");
			current[i] = aker[2][i] = scan.nextInt();

			//Varje åker får åtminstone minimal volym.
			volym -= current[i];
		}

		//Vattnar tills vattnet tar slut.
		while(volym>0)
		{
			//Indexet för den mest känsliga åkern.
			int i = findMostSensitive(aker[1]);

			//Ger åkern optimal volym.
			volym -= (aker[0][i]-current[i]);

			current[i] = aker[0][i];

			//Om vi inte hade så mycket vatten drar vi bort
			// så mycket vi översteg gränsen från åkern.
			if(volym<0)
			{
				current[i] -= (-1*volym);
			}
			else
			{
				//Annars ger vi åkern känslighet 0. Den är nöjd.
				aker[1][i] = 0;
			}
		}

		//Hur stor förlust.
		int loss = 0;

		for(int i = 0; i<antal; i++)
		{
			//Adderar skillnaden mellan uppnådd volym och optimal volym
			// multiplicerat med känsligheten till förlusten.
			loss += (aker[0][i]-current[i])*aker[1][i];
		}

		//Skriver ut svaret.
		System.out.println("Minimal förlust: " + loss);
	}
}