Sist endret: 23.09.2016  
 

Praksisoppgave - Seddeltrykkeriet

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 09.10.2017 15:00

Denne øvingen er ikke laget ferdig ennå.

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
seddeltrykkeriet.py, seddeltrykkeriet_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
seddeltrykkeriet.py Funksjonen maxValue(widths, heights, values, paperWidth, paperHeight)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 25
21

Seddeltrykkeriet

Det er ikke nødvendig å lese historien for å løse oppgaven.

Takket være din hjelp i øving 11 har dr. Gewalt bestemt seg for hvilket myntsett han vil bruke, og han har nå fått produsert tonnevis av mynter. Imidlertid begynner han nå å få vond rygg av å drasse rundt på en umåtelig mengde mynter, så han bestemmer seg for likevel å trykke sedler i tillegg. Alle skal selvfølgelig dekoreres med portretter av ham selv, og de skal trykkes på fint, dyrt papir med innlagt gull. Dermed er det viktig at minst mulig av papiret går til spille under trykkingen, samtidig som at verdien av sedlene han trykker blir størst mulig. Dessverre har han bare én maskin til å kutte opp papirarkene, og det eneste den maskinen kan gjøre er å ta et rektangulært ark og kutte det i to langs en horisontal eller vertikal linje. Kuttene kan attpåtil bare gjøres på heltallige centimeter. Papir som er for smalt eller kort til å kunne brukes til noen av sedlene er bortkastet. Papirfabrikken har dessuten prestert å sende ham papirark i hundrevis av forskjellige størrelser.

På grunn av det dyre papiret og de foreløpig begrensede finansene (han har jo ikke tatt over verden ennå, så myntene hans er lite verdt) vil dr. Gewalt prøve å få mest mulig ut av papirarkene. Gitt størrelsene og verdiene på sedlene og visse papirarkstørrelser lurer han derfor på hva som er den maksimale pengeverdien han kan få ut av hvert ark.

Oppgave

Du får oppgitt størrelsene og verdiene til en rekke rektangulære pengesedler som skal skjæres ut av rektangulære papirark av oppgitte størrelser. Utskjæringen kan kun foregå ved å gjøre et horisontalt eller et vertikalt kutt langs et rektangulært papirstykke, slik at du får to mindre rektangulære papirstykker. Et papirstykke kan enten brukes til en seddel, eller det kan kuttes videre opp, eller det må kastes fordi det er så lite at man ikke kan få flere sedler ut av det. Alle papirark og sedler har heltallig bredde og høyde, og kuttene kan kun gjøres slik at resultatene også får heltallige sider. Finn den maksimale seddelverdien man kan få ut av hvert av de opprinnelige papirarkene.

NB nr. 1: Hvilken vei sedlene vender (liggende eller stående) når man skjærer dem ut har ikke noe å si.
NB nr. 2: Det kan hende at noen av papirarkene er mindre enn noen av sedlene.
NB nr. 3: Det kan finnes flere sedler med samme størrelse.
NB nr. 4: Selv om man har et papirark som passer til en viss seddel, kan det hende at det lønner seg å kutte det videre opp til mindre sedler.

I eksempelinputen kan man få fem 2x3-sedler inn på det første arket, og en seddel av hver type på det andre arket.

Rammeverk

#!/usr/bin/python3

from sys import stdin


def max_value(widths, heights, values, paper_width, paper_height):
    # SKRIV DIN KODE HER


def main():
    widths = []
    heights = []
    values = []
    for triple in stdin.readline().split():
        dim_value = triple.split(':', 1)
        dim = dim_value[0].split('x', 1)
        width = int(dim[0][1:])
        height = int(dim[1][:-1])
        value = int(dim_value[1])
        widths.append(int(width))
        heights.append(int(height))
        values.append(int(value))
    for line in stdin:
        paper_width, paper_height = [int(x) for x in line.split('x', 1)]
        print((max_value(widths, heights, values, paper_width, paper_height)))


if __name__ == "__main__":
    main()

Variabelbeskrivelse

Input-eksempel

(2x3):5 (2x3):4 (4x5):16
10x3
7x4

Tilhørende output

25
21

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.