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

Published on 12 May 2024 09:40 PM
#Futurebasic

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

Source code in the futurebasic programming language

window 1, @"Knapsack Problem", (0,0,480,270)

_maxWeight = 400

void local fn FillKnapsack
  long              totalWeight = 0, totalValue = 0, itemWeight, unusedWeight
  CFDictionaryRef   item, extraItem = NULL
  SortDescriptorRef sd
  CFMutableArrayRef packedItems
  
  CFArrayRef items = @[
  @{@"item":@"map",                    @"weight":@9,   @"value":@150},
  @{@"item":@"compass",                @"weight":@13,  @"value":@35 },
  @{@"item":@"water",                  @"weight":@153, @"value":@200},
  @{@"item":@"sandwich",               @"weight":@50,  @"value":@160},
  @{@"item":@"glucose",                @"weight":@15,  @"value":@60 },
  @{@"item":@"tin",                    @"weight":@68,  @"value":@45 },
  @{@"item":@"banana",                 @"weight":@27,  @"value":@60 },
  @{@"item":@"apple",                  @"weight":@39,  @"value":@40 },
  @{@"item":@"cheese",                 @"weight":@23,  @"value":@30 },
  @{@"item":@"beer",                   @"weight":@52,  @"value":@10 },
  @{@"item":@"suntan cream",           @"weight":@11,  @"value":@70 },
  @{@"item":@"camera",                 @"weight":@32,  @"value":@30 },
  @{@"item":@"T-shirt",                @"weight":@24,  @"value":@15 },
  @{@"item":@"trousers",               @"weight":@48,  @"value":@10 },
  @{@"item":@"umbrella",               @"weight":@73,  @"value":@40 },
  @{@"item":@"waterproof trousers",    @"weight":@42,  @"value":@70 },
  @{@"item":@"waterproof overclothes", @"weight":@43,  @"value":@75 },
  @{@"item":@"note-case",              @"weight":@22,  @"value":@80 },
  @{@"item":@"sunglasses",             @"weight":@7,   @"value":@20 },
  @{@"item":@"towel",                  @"weight":@18,  @"value":@12 },
  @{@"item":@"socks",                  @"weight":@4,   @"value":@50 },
  @{@"item":@"book",                   @"weight":@30,  @"value":@10 }
  ]
  
  sd = fn SortDescriptorWithKey( @"value", NO )
  items = fn ArraySortedArrayUsingDescriptors( items, @[sd] )
  packedItems = fn MutableArrayWithCapacity(0)
  for item in items
    itemWeight = fn NumberIntegerValue(item[@"weight"])
    if ( totalWeight + itemWeight <= _maxWeight )
      MutableArrayAddObject( packedItems, item )
      totalWeight += itemWeight
      totalValue += fn NumberIntegerValue(item[@"value"])
    end if
  next
  
  text @"Menlo-Bold",,, fn ColorWithRGB(1.0,0.0,1.0,0.25),, 170
  print @"Item",@"Weight",@"Value"
  text @"Menlo",,, fn ColorClear
  for item in packedItems
    printf @"%@\t%6ld\t%5ld",item[@"item"],fn NumberIntegerValue(item[@"weight"]),fn NumberIntegerValue(item[@"value"])
  next
  text ,,, fn ColorWithRGB(1.0,0.0,1.0,0.25)
  printf @"knapsack\t%6ld\t%5ld",totalWeight,totalValue
  
  text
  print
  
  unusedWeight = _maxWeight - totalWeight
  
  for item in items
    if ( fn NumberIntegerValue(item[@"weight"]) <= unusedWeight )
      extraItem = item : break
    end if
  next
  
  if ( extraItem ) then printf @"There's just enough room for extra %@!", extraItem[@"item"]
end fn

fn FillKnapsack

HandleEvents

You may also check:How to resolve the algorithm Doubly-linked list/Definition step by step in the PowerShell programming language
You may also check:How to resolve the algorithm Binary strings step by step in the Ada programming language
You may also check:How to resolve the algorithm Write float arrays to a text file step by step in the Tcl programming language
You may also check:How to resolve the algorithm Convex hull step by step in the 11l programming language
You may also check:How to resolve the algorithm Proper divisors step by step in the Ceylon programming language