How to resolve the algorithm Knapsack problem/Unbounded step by step in the Wren programming language

Published on 12 May 2024 09:40 PM
#Wren

How to resolve the algorithm Knapsack problem/Unbounded step by step in the Wren programming language

Table of Contents

Problem Statement

A traveler gets diverted and has to make an unscheduled stop in what turns out to be Shangri La.   Opting to leave, he is allowed to take as much as he likes of the following items, so long as it will fit in his knapsack, and he can carry it. He knows that he can carry no more than   25   'weights' in total;   and that the capacity of his knapsack is   0.25   'cubic lengths'. Looking just above the bar codes on the items he finds their weights and volumes.   He digs out his recent copy of a financial paper and gets the value of each item.

He can only take whole units of any item, but there is much more of any item than he could ever carry

Show how many of each item does he take to maximize the value of items he is carrying away with him.

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knapsack problem/Unbounded step by step in the Wren programming language

Source code in the wren programming language

import "./fmt" for Fmt

class Item {
    construct new(name, value, weight, volume) {
        _name   = name
        _value  = value
        _weight = weight
        _volume = volume
    }

    name   { _name   }
    value  { _value  }
    weight { _weight }
    volume { _volume }
}

var items = [
    Item.new("panacea", 3000, 0.3, 0.025),
    Item.new("ichor", 1800, 0.2, 0.015),
    Item.new("gold", 2500, 2, 0.002)
]

var n = items.count
var count = List.filled(n, 0)
var best = List.filled(n, 0)
var bestValue = 0
var maxWeight = 25
var maxVolume = 0.25

var knapsack // recursive
knapsack = Fn.new { |i, value, weight, volume|
    if (i == n) {
        if (value > bestValue) {
            bestValue = value
            for (j in 0...n) best[j] = count[j]
        }
        return
    }
    var m1 = (weight / items[i].weight).floor
    var m2 = (volume / items[i].volume).floor
    count[i] = m1.min(m2)
    while (count[i] >= 0) {
        knapsack.call(
            i + 1,
            value  + count[i] * items[i].value,
            weight - count[i] * items[i].weight,
            volume - count[i] * items[i].volume
        )
        count[i] = count[i] - 1
    }
}

knapsack.call(0, 0, maxWeight, maxVolume)
System.print("Item Chosen  Number Value  Weight  Volume")
System.print("-----------  ------ -----  ------  ------")
var itemCount = 0
var sumNumber = 0
var sumWeight = 0
var sumVolume = 0
for (i in 0... n) {
    if (best[i] != 0) {
        itemCount  = itemCount + 1
        var name   = items[i].name
        var number = best[i]
        var value  = items[i].value  * number
        var weight = items[i].weight * number
        var volume = items[i].volume * number
        sumNumber  = sumNumber + number
        sumWeight  = sumWeight + weight
        sumVolume  = sumVolume + volume
        Fmt.write("$-11s   $2d    $5.0f   $4.1f", name, number, value, weight)
        Fmt.print("    $4.2f", volume)
    }
}
System.print("-----------  ------ -----  ------  ------")
Fmt.write("$d items       $2d    $5.0f   $4.1f", itemCount, sumNumber, bestValue, sumWeight)
Fmt.print("    $4.2f", sumVolume)

You may also check:How to resolve the algorithm Tree traversal step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Babbage problem step by step in the Smalltalk programming language
You may also check:How to resolve the algorithm Pseudo-random numbers/Combined recursive generator MRG32k3a step by step in the Kotlin programming language
You may also check:How to resolve the algorithm Compile-time calculation step by step in the Common Lisp programming language
You may also check:How to resolve the algorithm Set consolidation step by step in the ooRexx programming language