Kombinationer

Altså, de vejer alle sammen noget forskelligt, og du vil finde den sammensætning der er tættest på at veje 5kg? Og du vil gerne lave et program der regner og returnerer hvad de spande der er blevet fundet, vejer, og hvilke spande det er?

Hej Martin

Ja de vejer alle sammen noget forskelligt, programmet skal så finde den kombination af spande der tilsammen giver et resultat der er tættest på 5 kg men ikke under 5 kg , alle kombinationer af spande må bruges

Se illustration. https://en.m.wikipedia.org/wiki/File:KombinationMehrkopfwaage.jpg

Jeg tænker det er noget med brute force vi er ovre i

Dit problem lyder som en instans af 0/1 Knapsack

Pseudo-kode kan findes i 0/1 knapsack problem afsnittet under Solving på nedenstående link:

https://en.wikipedia.org/wiki/Knapsack_problem

For,at formulere dit problem som 0/1 knapsack skal du beregne den totale vægt af alle spande. Din target vægt i knapsack er så total - 5kg, og din værdi for hver spand er 1. Når du har den optimale løsning her, finder du løsningen på dit oprindelige problem ved at tage alle de spande der ikke er med...

Se evt svaret her:

http://stackoverflow.com/questions/7949705/variation-on-knapsack-minimum-total-value-exceeding-w

Her er en implementation i c

http://basiccodings.blogspot.dk/2013/04/01-knapsack-problem-in-c.html

Hej Jacob

Du har ikke et eksempel på knapsack skrevet i struktureret text?

et andet sted at finde code til Knapsack er
http://rosettacode.org/wiki/Knapsack_problem/0-1
hvis man scroller lidt ned af siden kommer en liste af programmerings sprog coden er vist i

Pseudocode

samlet_vægt = 0
vægt_grænse = 5kg

loop start
tag vigtigste item der er tilbage, læg item_vægt til samlet_vægt, 
er vi over vægt_grænsen ?? 
hvis ja læg tilbage, træk vægten fra samlet_vægt igen
hvis nej lig den i tasken
loop slut (ikke flere items i listen over de tilgængelige)

så skal det "bare" omskrives lidt, så den går lige over 5kg