How to resolve the algorithm Knapsack problem/Continuous step by step in the PureBasic programming language
Published on 12 May 2024 09:40 PM
How to resolve the algorithm Knapsack problem/Continuous step by step in the PureBasic programming language
Table of Contents
Problem Statement
A thief burgles a butcher's shop, where he can select from some items. The thief knows the weights and prices of each items. Because he has a knapsack with 15 kg maximal capacity, he wants to select the items such that he would have his profit maximized. He may cut the items; the item has a reduced price after cutting that is proportional to the original price by the ratio of masses. That means: half of an item has half the price of the original.
This is the item list in the butcher's shop:
Show which items the thief carries in his knapsack so that their total weight does not exceed 15 kg, and their total value is maximized.
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Knapsack problem/Continuous step by step in the PureBasic programming language
Source code in the purebasic programming language
Structure item
name.s
weight.f ;units are kilograms (kg)
Value.f
vDensity.f ;the density of the value, i.e. value/weight, and yes I made up the term ;)
EndStructure
#maxWeight = 15
Global itemCount = 0 ;this will be increased as needed to match actual count
Global Dim items.item(itemCount)
Procedure addItem(name.s, weight.f, Value.f)
If itemCount >= ArraySize(items())
Redim items.item(itemCount + 10)
EndIf
With items(itemCount)
\name = name
\weight = weight
\Value = Value
If Not \weight
\vDensity = \Value
Else
\vDensity = \Value / \weight
EndIf
EndWith
itemCount + 1
EndProcedure
;build item list
addItem("beef", 3.8, 36)
addItem("pork", 5.4, 43)
addItem("ham", 3.6, 90)
addItem("greaves", 2.4, 45)
addItem("flitch", 4.0, 30)
addItem("brawn", 2.5, 56)
addItem("welt", 3.7, 67)
addItem("salami", 3.0, 95)
addItem("sausage", 5.9, 98)
SortStructuredArray(items(), #PB_Sort_descending, OffsetOf(item\vDensity), #PB_Sort_Float, 0, itemCount - 1)
Define TotalWeight.f, TotalValue.f, i
NewList knapsack.item()
For i = 0 To itemCount
If TotalWeight + items(i)\weight < #maxWeight
AddElement(knapsack())
knapsack() = items(i)
TotalWeight + items(i)\weight
TotalValue + items(i)\Value
Else
AddElement(knapsack())
knapsack() = items(i)
knapsack()\weight = #maxWeight - TotalWeight
knapsack()\Value = knapsack()\weight * knapsack()\vDensity
TotalWeight = #maxWeight
TotalValue + knapsack()\Value
Break
EndIf
Next
If OpenConsole()
PrintN(LSet("Maximal weight", 26, " ") + "= " + Str(#maxWeight) + " kg")
PrintN(LSet("Total weight of solution", 26, " ") + "= " + Str(#maxWeight) + " kg")
PrintN(LSet("Total value", 26, " ") + "= " + StrF(TotalValue, 3) + " " + #CRLF$)
PrintN("You can carry the following materials in the knapsack: ")
ForEach knapsack()
PrintN(RSet(StrF(knapsack()\weight, 1), 5, " ") + " kg " + LSet(knapsack()\name, 10, " ") + " (Value = " + StrF(knapsack()\Value, 3) + ")")
Next
Print(#CRLF$ + #CRLF$ + "Press ENTER to exit")
Input()
CloseConsole()
EndIf
You may also check:How to resolve the algorithm Apply a callback to an array step by step in the min programming language
You may also check:How to resolve the algorithm Special variables step by step in the Raku programming language
You may also check:How to resolve the algorithm Arithmetic evaluation step by step in the Amazing Hopper programming language
You may also check:How to resolve the algorithm Averages/Median step by step in the FutureBasic programming language
You may also check:How to resolve the algorithm Carmichael 3 strong pseudoprimes step by step in the PARI/GP programming language