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

Published on 12 May 2024 09:40 PM
#Seed7

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

Source code in the seed7 programming language

$ include "seed7_05.s7i";
  include "float.s7i";

const type: bounty is new struct
    var integer: value is 0;
    var float: weight is 0.0;
    var float: volume is 0.0;
  end struct;

const func bounty: bounty (in integer: value, in float: weight, in float: volume) is func
  result
    var bounty: bountyVal is bounty.value;
  begin
    bountyVal.value := value;
    bountyVal.weight := weight;
    bountyVal.volume := volume;
  end func;

const proc: main is func
  local
    const bounty: panacea is bounty(3000, 0.3, 0.025);
    const bounty: ichor   is bounty(1800, 0.2, 0.015);
    const bounty: gold    is bounty(2500, 2.0, 0.002);
    const bounty: sack    is bounty(0,   25.0, 0.25);
    const integer: maxPanacea is trunc(min(sack.weight / panacea.weight, sack.volume / panacea.volume));
    const integer: maxIchor   is trunc(min(sack.weight / ichor.weight,   sack.volume / ichor.volume));
    const integer: maxGold    is trunc(min(sack.weight / gold.weight,    sack.volume / gold.volume));
    var bounty: current is bounty.value;
    var bounty: best is bounty.value;
    var array integer: bestAmounts is 3 times 0;
    var integer: numPanacea is 0;
    var integer: numIchor is 0;
    var integer: numGold is 0;
  begin
    for numPanacea range 0 to maxPanacea do
      for numIchor range 0 to maxIchor do
        for numGold range 0 to maxGold do
          current.value  := numGold      * gold.value  + numIchor      * ichor.value  + numPanacea      * panacea.value;
          current.weight := flt(numGold) * gold.weight + flt(numIchor) * ichor.weight + flt(numPanacea) * panacea.weight;
          current.volume := flt(numGold) * gold.volume + flt(numIchor) * ichor.volume + flt(numPanacea) * panacea.volume;
          if current.value > best.value and current.weight <= sack.weight and current.volume <= sack.volume then
            best := current;
            bestAmounts := [] (numPanacea, numIchor, numGold);
          end if;
        end for;
      end for;
    end for;
    writeln("Maximum value achievable is " <& best.value);
    writeln("This is achieved by carrying " <& bestAmounts[1] <& " panacea, " <& bestAmounts[2] <& " ichor and " <& bestAmounts[3] <& " gold items");
    writeln("The weight of this carry is " <& best.weight <& " and the volume used is " <& best.volume digits 4);
  end func;

You may also check:How to resolve the algorithm Loops/For with a specified step step by step in the Tcl programming language
You may also check:How to resolve the algorithm Reverse a string step by step in the Euphoria programming language
You may also check:How to resolve the algorithm File modification time step by step in the Clojure programming language
You may also check:How to resolve the algorithm Find limit of recursion step by step in the Phixmonti programming language
You may also check:How to resolve the algorithm Sorting algorithms/Cocktail sort step by step in the M2000 Interpreter programming language