How to resolve the algorithm Knapsack problem/0-1 step by step in the Oz programming language

Published on 12 May 2024 09:40 PM
#Oz

How to resolve the algorithm Knapsack problem/0-1 step by step in the Oz programming language

Table of Contents

Problem Statement

A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature, so he needs to pack well for the trip. He has a good knapsack for carrying things, but knows that he can carry a maximum of only 4kg in it,   and it will have to last the whole day. He creates a list of what he wants to bring for the trip but the total weight of all items is too much. He then decides to add columns to his initial list detailing their weights and a numerical value representing how important the item is for the trip.

Here is the list:

The tourist can choose to take any combination of items from the list, but only one of each item is available. He may not cut or diminish the items, so he can only take whole units of any item.

Show which items the tourist can carry in his knapsack so that their total weight does not exceed 400 dag [4 kg],   and their total value is maximized. [dag = decagram = 10 grams]

Let's start with the solution:

Step by Step solution about How to resolve the algorithm Knapsack problem/0-1 step by step in the Oz programming language

Source code in the oz programming language

declare
  %% maps items to pairs of Weight(hectogram) and Value
  Problem = knapsack('map':9#150
                     'compass':13#35
                     'water':153#200
                     'sandwich':50#160
                     'glucose':15#60
                     'tin':68#45 
                     'banana':27#60 
                     'apple':39#40 
                     'cheese':23#30 
                     'beer':52#10 
                     'suntan cream':11#70 
                     'camera':32#30 
                     't-shirt':24#15 
                     'trousers':48#10 
                     'umbrella':73#40 
                     'waterproof trousers':42#70 
                     'waterproof overclothes':43#75 
                     'note-case':22#80 
                     'sunglasses':7#20 
                     'towel':18#12 
                     'socks':4#50 
                     'book':30#10
                    )

  %% item -> Weight
  Weights = {Record.map Problem fun {$ X} X.1 end}
  %% item -> Value
  Values =  {Record.map Problem fun {$ X} X.2 end}

  proc {Knapsack Solution}
     %% a solution maps items to finite domain variables
     %% with the domain {0,1}
     Solution = {Record.map Problem fun {$ _} {FD.int 0#1} end}
     %% no more than 400 hectograms
     {FD.sumC Weights Solution '=<:' 400} 
     %% search through valid solutions
     {FD.distribute naive Solution}
  end
 
  proc {PropagateLargerValue Old New}
     %% propagate that new solutions must yield a higher value
     %% than previously found solutions (essential for performance)
     {FD.sumC Values New '>:' {Value Old}} 
  end

  fun {Value Candidate}
     {Record.foldL {Record.zip Candidate Values Number.'*'} Number.'+' 0}
  end
  
  fun {Weight Candidate}
     {Record.foldL {Record.zip Candidate Weights Number.'*'} Number.'+' 0}
  end

  [Best] = {SearchBest Knapsack PropagateLargerValue}
in
  {System.showInfo "Items: "}
  {ForAll
     {Record.arity {Record.filter Best fun {$ T} T == 1 end}}
     System.showInfo}
  {System.printInfo "\n"}
  {System.showInfo "total value: "#{Value Best}}
  {System.showInfo "total weight: "#{Weight Best}}

You may also check:How to resolve the algorithm Maze generation step by step in the BASIC programming language
You may also check:How to resolve the algorithm Regular expressions step by step in the Standard ML programming language
You may also check:How to resolve the algorithm Execute Brain step by step in the Objeck programming language
You may also check:How to resolve the algorithm OpenGL step by step in the Haskell programming language
You may also check:How to resolve the algorithm Convert decimal number to rational step by step in the Mathematica / Wolfram Language programming language