Example of Coding on haXe (SnapSack Algorithm) – Part 7

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.

Share

haXe examples

Here are some examples of code on haXe

Share