Sist endret: 23.09.2016  
 

Praksisoppgave - Seddeltrykkeriet

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 09.10.2017 15:00

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

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å.