How to resolve the algorithm Knapsack problem/Continuous step by step in the Ursala programming language

Published on 12 May 2024 09:40 PM
#Ursala

How to resolve the algorithm Knapsack problem/Continuous step by step in the Ursala 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 Ursala programming language

Source code in the ursala programming language

#import flo
#import lin

items = # name: (weight,price)

<
   'beef   ': (3.8,36.0),
   'pork   ': (5.4,43.0),
   'ham    ': (3.6,90.0),
   'greaves': (2.4,45.0),
   'flitch ': (4.0,30.0),
   'brawn  ': (2.5,56.0),
   'welt   ': (3.7,67.0),
   'salami ': (3.0,95.0),
   'sausage': (5.9,98.0)>

system = # a function to transform the item list to the data structure needed by the solver

linear_system$[
   lower_bounds: *nS ~&\0.,         # all zeros because we can't steal less than zero
   upper_bounds: ~&nmlPXS,          # can't steal more than what's in the shop
   costs: * ^|/~& negative+ vid,    # prices divided by weights, negated so as to maximize
   equations: ~&iNC\15.+ 1.-*@nS]   # 1 equation constraining the total weight to 15

#cast %em

main = solution system items

You may also check:How to resolve the algorithm Peano curve step by step in the AutoHotkey programming language
You may also check:How to resolve the algorithm Quad-power prime seeds step by step in the Wren programming language
You may also check:How to resolve the algorithm Execute HQ9+ step by step in the 11l programming language
You may also check:How to resolve the algorithm First-class functions/Use numbers analogously step by step in the Ada programming language
You may also check:How to resolve the algorithm Barnsley fern step by step in the Standard ML programming language