Saturday, February 19, 2022

Casio fx-9750GIII: 0-1 Knapsack Problem

Casio fx-9750GIII: 0-1 Knapsack Problem


What Do I Take?


Imagine you are given a list of objects, which each object has its profit value and it's associated weight.  You are given a knapsack, which is also known as a backpack, which can carry a limited amount of weight.  Your task is to select the objects with the most value that can fit in the knapsack.


In a 0-1 Knapsack Problem, each object can not be broken up into pieces.  There is a problem where that is allowed, known as the Fractional Knapsack Problem.  


One approach is to use what is known as the greedy algorithm.  In the greedy algorithm, you select the best choice at the moment at each step.   Once an object is selected, you go on to the next step.  There is no reverse or correction.  The greedy algorithm lives by the philosophy of "no regrets".  


Please be aware, even with attempt to select the best choice at each step, we may still not have the optimal solution.   


You can choose which criteria is used for selecting the best option.  For the program 01KNAPS, this criteria is used:


1.  The maximum ratio value of value to weight

2.  If the ratio is a tie, the maximum value 


Introduction to the Program 01KNAPS - Casio fx-9750GIII


Inputs:

List of Values of Each Object:  stored in List 10

List of Weights of Each Object:  stored in List 11

Capacity of the Knapsack:  stored in M


Outputs:

Total Value/Profit Made:   stored in P

Weight Remaining:  stored in M

A matrix showing which objects are selected, along with their weights, and value to weight ratio.   Columns are stored in List 14, List 15, and List 16, respectively.  Zeroes mean that the object is not selected.  


Notes:


The Wait Loop


The program starts with an intro screen created with several Locate statements and a For loop used as a "Wait".   This is 100% optional and serves to tell the user what program they are running.


A "Wait" Loop:

For I→1 To 750 (or a suitable number to create a short wait, 1/4 to 1/2 second)

Next


I aim to give a title screen to programs when possible.  


The SortD Function


In the MENU-LIST function in the program editor screen, we can sort lists by using the SortA (ascending) or SortD (descending).   We can sort a list by itself, or a list using up to five sub-lists.  The sorted lists are saved automatically.


It's not perfect, but it's better than nothing.


By the way, the function can be found in the CATALOG in certain times:  in the program editor or in the RUN-MAT mode (main) if the Linear Input is selected.   


Casio fx-9750GIII Program:  01KNAPS

(452 bytes)


ClrText

Locate 1,1,"0-1 KNAPSACK"

Locate 1,2,"PROBLEM BY"

Locate 1,3,"GREEDY ALG"

Locate 1,4,"EWS 2022-01-08"

For 1→I To 750

Next


ClrText

"LIST OF VALUES"?→List 10

"LIST OF WEIGHTS"?→List 11

"CAPACITY"?→M

List 10→List 12

0→P

List 10÷List 11→List 12

Dim List 12→Dim List 13

SortD(List 12, List 10, List 11)


For 1→I To Dim List 10

If List 11[ I ]≤M

Then

List 10[ I ]+P→P

M-List 11[ I ]→M

1→List 13[ I ]

IfEnd

Next


List 13×List 10→List 14

List 13×List 11→List 15

List 13×List 12→List 16


ClrText

Locate 1,3,"TOTAL VALUE:"

Locate 3,4,P

Locate 1,6,"WEIGHT LEFT:"

Locate 3,7,M◢

List→Mat(List 14,List 15,List 16)


Examples


Example 1:

Values:  {5, 3, 8, 4, 8, 4, 8}

Weights: {1, 1, 2,4, 2, 2, 4}

Capacity: 10


Total Value:  28

Weight Left: 2

[ [ 5, 1, 5 ]

[ 8, 2, 4 ]

[ 8, 2, 4 ]

[ 3, 1, 3 ]

[ 4, 2, 2 ]

[ 0, 0, 0 ] 

[ 0, 0, 0 ]]



Example 2:

Values: {20, 24, 22, 30, 25, 30}

Weights: {4, 6, 2, 6, 5, 5}

Capacity: 15


Total Value: 72

Weight Left: 4

[[22, 2, 11]

[30, 5, 6]

[20, 4, 5]

[0, 0, 0]

[0, 0, 0]

[0, 0, 0]]


Source


"Basics of Greedy Algorithms"  HackerEarth. 2022.  https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/   Retrieved January 6, 2022.


Eddie


All original content copyright, © 2011-2022.  Edward Shore.   Unauthorized use and/or unauthorized distribution for commercial purposes without express and written permission from the author is strictly prohibited.  This blog entry may be distributed for noncommercial purposes, provided that full credit is given to the author.