Posted by In this example you will see: Snapsack algorithm using multi-dimensional arrays
NOTIFICATION: These examples are provided for educational purposes. Using this code is under your own responsibility and risk. The code is given ‘as is’. I do not take responsibilities of how they are used.
example_7.hx:
/**
* @author: Alejandro G. Carlstein R. M.
*/
class Item{
public var name : String;
public var weight : Int;
public var value : Int;
public function new(?name : String, ?weight : Int, ?value : Int){
this.name = (name == null) ? '' : name;
this.weight = (weight == null) ? 0 : weight;
this.value = (value == null) ? 0 : value;
}
public function setName(name : String) : Void{
this.name = (name == null) ? '' : name;
}
public function getName() : String{
return this.name;
}
public function setWeight(weight : Int) : Void{
this.weight = weight;
}
public function getWeight() : Int{
return this.weight;
}
public function setValue(value : Int) : Void{
this.value = value;
}
public function getValue() : Int{
return this.value;
}
}
/* Our dynamic programming table element.
* We have the value that we can store, and
* also a way to remember what we selected.
*/
class Prog{
public var value : Int;
public var prev_row : Int;
public var prev_column : Int;
public function new(?prev_row : Int, ?prev_column : Int, ?value : Int){
this.value = (value == null) ? 0 : value;
this.prev_row = (prev_row == null) ? -1 : prev_row;
this.prev_column = (prev_column == null) ? -1 : prev_column;
}
public function setValue(value : Int) : Void{
this.value = value;
}
public function getValue() : Int{
return this.value;
}
public function setPrevRow(prev_row : Int) : Void{
this.prev_row = prev_row;
}
public function getPrevRow() : Int{
return this.prev_row;
}
public function setPrevColumn(prev_column : Int) : Void{
this.value = prev_column;
}
public function getPrevColumn() : Int{
return this.prev_column;
}
}
class Snapsack{
private var items : Array<Item>;
private var selected_items : Array<Item>;
private var table : Array<Array<Prog>>;
private var max_weight : Int;
private var num_items : Int;
private var total_weight : Int;
private var total_value : Int;
private function initTable() : Void{
trace('initTable()');
var i : Int = 0;
var j : Int = 0;
for (i in 0...num_items) {
table[i] = new Array<Prog>();
for (j in 0...max_weight) {
table[i][j] = new Prog(0, 0, 0);
}
}
}
private function initItems(){
trace('initItems()');
var i : Int = 0;
for (i in 0...num_items){
items[i] = new Item('', 0, 0);
}
}
private function printTable() : Void{
trace('printTable()');
var str : String = '';
var i : Int = 0;
var j : Int = 0;
for (i in 0...table.length) {
for (j in 0...max_weight) {
str += '[(' +
table[i][j].prev_row +
', ' +
table[i][j].prev_column +
') ' +
table[i][j].value +
']';
}
trace(str);
str = '';
}
}
private function printItems(){
trace('printItems()');
var i : Int = 0;
for (i in 0...num_items){
trace('name: ' +
items[i].name +
', weight: ' +
items[i].weight +
', value: ' +
items[i].value);
}
}
public function new(num_items : Int, max_weight : Int){
this.num_items = num_items;
this.max_weight = ++max_weight;
total_weight = 0;
total_value = 0;
items = new Array<Item>();
table = new Array<Array<Prog>>();
table.push(new Array<Prog>());
for (i in 0...max_weight) {
table[table.length - 1][i] = new Prog(-1, -1, 0);
}
}
public function pushItem(name : String, weight : Int, value : Int){
items.push(new Item(name, weight, value));
table.push(new Array<Prog>());
var i : Int = 0;
for (i in 0...max_weight) {
table[table.length - 1][i] = new Prog(-1, -1, 0);
}
}
public function pickItems() : Void {
printTable();
printItems();
var i : Int = 1;
var w : Int = 0;
// Perform knapsack and find maximun value
for (i in 1...num_items + 1){
for (w in 0...max_weight){
table[i][w].prev_row = i - 1;
table[i][w].prev_column = w;
// Check if item fit inside the knapsack
if(items[i - 1].weight <= w) {
var diff_weight : Int = w - items[i - 1].weight;
// Check which value is higher
table[i][w].value = Math.round(Math.max((items[i - 1].value + table[i - 1][diff_weight].value),
table[i - 1][w].value));
// Keep track of the previous column
if(table[i][w].value > table[i - 1][w].value)
table[i][w].prev_column = diff_weight;
}else{
table[i][w].value = table[i - 1][w].value;
}
}
}
total_value = table[num_items - 1][max_weight - 1].value;
total_weight = 0;
var w : Int = max_weight - 1;
var t : Int = 0;
selected_items = new Array<Item>();
var i : Int = num_items - 1;
while (i > 0){
if(table[i][w].value != table[i - 1][w].value){
total_weight += items[i - 1].weight;
selected_items.push(new Item(items[i - 1].name,
items[i - 1].weight,
items[i - 1].value));
}
t = w;
w = table[i][w].prev_column;
i = table[i][t].prev_row;
}
printTable();
}
public function getTotalValue() : Int{
return total_value;
}
public function getTotalWeight() : Int{
return total_weight;
}
public function printResult() : Void{
for (i in 0...selected_items.length)
trace('name: ' +
selected_items[i].name +
', weight: ' +
selected_items[i].weight +
', value: ' +
selected_items[i].value);
}
}
class Example_7 {
static function main(){
trace('Creating Snapsack');
var snapsack : Snapsack = new Snapsack(4, 5);
trace('adding items to snapsack');
snapsack.pushItem('item_A', 2, 3);
snapsack.pushItem('item_B', 3, 4);
snapsack.pushItem('item_C', 4, 5);
snapsack.pushItem('item_D', 5, 6);
snapsack.pickItems();
trace('Total value: ' + snapsack.getTotalValue());
trace('Total Weight: ' + snapsack.getTotalWeight());
snapsack.printResult();
}
}
If you encounter any problems or errors, please let me know by providing an example of the code, input, output, and an explanation. Thanks.
© 2010, Alejandro G. Carlstein Ramos Mejia. All rights reserved.
