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.