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.

© 2010, Alejandro G. Carlstein Ramos Mejia. All rights reserved.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

*

Click to Insert Smiley

SmileBig SmileGrinLaughFrownBig FrownCryNeutralWinkKissRazzChicCoolAngryReally AngryConfusedQuestionThinkingPainShockYesNoLOLSillyBeautyLashesCuteShyBlushKissedIn LoveDroolGiggleSnickerHeh!SmirkWiltWeepIDKStruggleSide FrownDazedHypnotizedSweatEek!Roll EyesSarcasmDisdainSmugMoney MouthFoot in MouthShut MouthQuietShameBeat UpMeanEvil GrinGrit TeethShoutPissed OffReally PissedMad RazzDrunken RazzSickYawnSleepyDanceClapJumpHandshakeHigh FiveHug LeftHug RightKiss BlowKissingByeGo AwayCall MeOn the PhoneSecretMeetingWavingStopTime OutTalk to the HandLoserLyingDOH!Fingers CrossedWaitingSuspenseTremblePrayWorshipStarvingEatVictoryCurseAlienAngelClownCowboyCyclopsDevilDoctorFemale FighterMale FighterMohawkMusicNerdPartyPirateSkywalkerSnowmanSoldierVampireZombie KillerGhostSkeletonBunnyCatCat 2ChickChickenChicken 2CowCow 2DogDog 2DuckGoatHippoKoalaLionMonkeyMonkey 2MousePandaPigPig 2SheepSheep 2ReindeerSnailTigerTurtleBeerDrinkLiquorCoffeeCakePizzaWatermelonBowlPlateCanFemaleMaleHeartBroken HeartRoseDead RosePeaceYin YangUS FlagMoonStarSunCloudyRainThunderUmbrellaRainbowMusic NoteAirplaneCarIslandAnnouncebrbMailCellPhoneCameraFilmTVClockLampSearchCoinsComputerConsolePresentSoccerCloverPumpkinBombHammerKnifeHandcuffsPillPoopCigarette