Tävlingsprogrammering/Uppgifter/Betygsoptimering

Betygsoptimering

Albert är student, men har väldigt lite tid. Trots detta vill han ha så höga betyg som möjligt i skolan. Just nu läser Albert N stycken kurser samtidigt, och på varje kurs kan man få K olika betyg, från 0 till K-1. Varje kurs avslutas med en tentamen, och alla tentor går ungefär samtidigt så pluggandet måste ske innan tentorna börjar. Den j:te tentamen har betygsgränserna B_j,1, B_j,2,...,B_j,K-1. Albert har totalt T timmar kvar att plugga på. Han har räknat ut att för att få varje poäng på den j:te tentamen måste han plugga P_j timmar. Beräkna hur Albert skall plugga för att summan av hans betyg skall bli så hög som möjligt.

Indata

Första raden består av heltalen N, K och T. Därefter följer en rad med N mellanslagsseparerade heltal: P₁,P₂, ..., P_N. Till sist följer N rader med K-1 heltal vardera, betygsgränserna för varje ämne (det i:te talet på den j:te raden är alltså B_j,i). T och B_j,i är mellan 2 och 20'000. De övriga värdena (N, K, P_i) är mellan 2 och 100. Strikt bättre betyg har alltid strikt högre poäng, d.v.s. B_j,i > B_j,i-1.

Utdata

Ett heltal, summan av betygen Albert får vid bästa pluggning.

Exempel 1: Indata

3 2 100
5 2 20
15
25
2

Exempel 1: Utdata

2

Förklaring: Vi har inte råd med att få (1) i den första kursen som kräver mest arbete.

Exempel 2: Indata

4 4 129
2 3 4 5
5 15 35
4 12 35
10 11 12
2 3 50

Exempel 2: Utdata

9

Förklaring: Här måste vi plugga riktigt genomtänkt. Om vi nöjer oss med betyget (2) i ämnena 1,2 och 4 och satsar på maxbetyget (3) i det tredje ämnet så kommer vi få hela 9 i totalbetyg. Tidsåtgången blir 2*15+3*12+4*12+5*3 = 129. Puh...

Lösning

Detta är en variant av knapsack-problemet och kan lösas med dynamisk programmering. Man kan t.ex. loopa över kurserna och spara i en tabell den minimala pluggtid som krävs för att uppnå varje möjligt totalbetyg på de hittills genomloopade kurserna. När man tar en ny kurs går man igenom tabellen och testar vad betyget respektive tidsåtgången blir om man, utgående från detta gamla totalbetyg, pluggar sig till vart och ett av de K betygen på den nya kursen. Om tidsåtgången är bättre än den hittills hittade för detta totalbetyg ersätter man den i tabellen. För att undvika att skriva över sig själv (så att man kan få två betyg på samma kurs eller liknande) kan man ha två arrayer som man bara kopierar när man börjar med en ny kurs. Observera att man alltid kan avbryta sökningen när tidsåtgången överstiger T, allt över detta är ointressant (här använder man sig av att strikt bättre betyg behöver strikt högre pluggtid). Då har man också automatiskt det maximala totalbetyget på slutet.

Lösning i C:

#include <stdio.h>

int main() {
  int N,K,T,P[100],B[100][101],t[10001],u[10001],i,j,k;
  scanf("%d %d %d", &N, &K, &T);
  for(i=0;i<N;i++) scanf("%d", &P[i]);
  for(i=0;i<N;i++) {
    B[i][0]=0;
    for(j=1;j<K;j++) scanf("%d", &B[i][j]);
  }
  for(i=0;i<=N*K;i++) t[i]=u[i]=1000000;   //Sätt oändlig tidsåtgång för alla totalbetyg 
  t[0]=u[0]=0;                            //...utom betyget 0 som är gratis. 
  for(i=0;i<N;i++) {      //Loopa över kurserna 
    for(j=0;t[j]<T;j++) {    //Loopa över alla sedan tidigare möjliga totalbetyg j som kräver mindre än T timmars plugg 
      for(k=0;k<K;k++) {    //Loopa över de möjliga betygen k på kursen 
        if(t[j]+P[i]*B[i][k]<u[j+k]) u[j+k]=t[j]+P[i]*B[i][k];    //Med dessa val erhålls betyget j+k. Tidsåtgången blir t[j]+P[i]*B[i][k]. Uppdatera tabellen om detta är bättre än tidigare bästalösning. 
      }
    }
    for(j=0;u[j]<=T;j++) {t[j]=u[j];}   //Kopiera tabellen från u till t.
  }
  printf("%d\n", j-1);   //Det sista j som gav u[j]<=T utgör svaret på uppgiften.
  return 0;
}