Någon som kan förklara Hur man på enklast sätt kan räkna ut detta?
Du har rör som är 10 meter långa. Din uppgift är att kapa dessa med så få spill bitar som möjligt
60 längder som ska bli 3 meter
49 längder som ska bli 4 meter
12 längder som ska bli 7 meter
Vilket är det minsta antal rör av längd 10 meter man behöver?
Det jag är intresserad av att veta är HUR man räknar ut det med någon formel.
Genom att kapa de 12 som ska bli 7m får man ju även 12 st 3m bitar((7+3=10)
man kan ju få ut 2 st 3m bitar även av att kapa 4m bitar (4+3+3=10)
men det måste ju finnas något smidigare sätt att räkna ut det i en formel?
vill tillägga att svaret blir ju 49
mitt sätt att räkna ut det på är följande:
de 12 långa bitarna ger 12 bitar samt plockar bort 12 st bitar ifrån de 60 3 meters bitarna(48 kvar)
steg 2 dela 48 med 2 ger 24 st 7 meters bitar samt tar bort de resterande 3 meters bitarna.
då finns 13 bitar kvar.
man räknar då ihop 24+12+13= 49
Välkommen till Pluggakuten!
Jag tror inte att det finns en formel, man måste nog tänka själv.
För att få fram 12 längder som är 7 m behövs det 12 rör, och då blir det även 12 3 m-längder.
För att få fram 48 längder som är 4 m behövs det 48 rör, och då blir det även 96 3 m-längder. Det är för många.
Om vi istället gör 48 (=60-12) längder som är 3 m får vi samtidigt 24 längder som är 4 m långa av 24 rör.
Då gör vi 24 stycke 4-m-längder av 12 stycken rör, (det blir en massa 2 m-längder över) och så använder vi ett sista rör till den sista längden. Totalt blir det 12+24+12+1 = 49 rör.
Det vore trevligt om någon annan kunde hitta en bättre lösning, som ger mindre spill.
Jag kan tänka mig att det här är ett svårt problem i det generella fallet (NP-fullständigt i så fall).
Men här blir det enkelt genom att en rörlängd (7) bara går en gång i 10, och dessutom det som blir över (3) är något som vi vill ha.
Vad innebär N-P fullständig?
Det är en klass av problem. Tiden det tar att lösa ett sådant växer exponentiellt med storleken på problemet, tror man. Men det är inte bevisat.
https://sv.wikipedia.org/wiki/NP-fullst%C3%A4ndig
Läs gärna den engelska sidan också, den är mycket fylligare.
