Knapsack problem using simulated annealing

The knapsack problem ( Wiki link ) is a problem in combinatorial optimisation. Given a set of items, each with a weight and a value, determine the number of each item to include in a collection so that the total weight is less than or equal to a given limit and the total value is as large as possible. Let's see how we can solve it using simulated annealing.

A Basic Understanding

Suppose we are planning a hiking trip; and we are, therefore, interested in filling a knapsack with items that are considered necessary for the trip. There are N different item types that are deemed desirable; these could include bottle of water, apple, orange, sandwich, and so forth. Each item type has a given set of two attributes, namely a weight (or volume) and a value that quantifies the level of importance associated with each unit of that type of item. Since the knapsack has a limited weight (or volume) capacity, the problem of interest is to figure out how to load the knapsack with a combination of units of the specified types of items that yields the greatest total value. What we have just described is called the knapsack problem.

Implementation

knapsack.js

/**
 * Will hold each knapsack item
 */
function Item(w,v,index){
 this.weight = w; //Weight of the item
 this.value = v;  //Weight of the value
 this.index = index; //Index of the value
 this.print = function(){
  document.write("Item : w : "+this.weight+", v : "+this.value+"<br/>");
 }
}

/**
 * Knapsack bag
 */
function Bag(size){
 
 this.size = size;
 this.itemset = []; //Will hold the overall dataset
 this.currentSolution = []; //will hold the current solution
 
 /**
  * Populates the itemset with the dataset provided above
  */
 this.prepare = function(){
  for(var i = 0;i<dataset.length;i++){
   var item = new Item(dataset[i][0],dataset[i][1],i);
   this.itemset.push(item);
  }
  var temp = getRandomAsInt(0,this.itemset.length);
  this.currentSolution.push(this.getItemBasedOnIndex(this.itemset, temp));
 }
 
 /**
  * Gets the items from the itemset provided as an argument based on the index
  */
 this.getItemBasedOnIndex = function(itemset,index){
  var item = null;
  for(var i=0;i<itemset.length;i++){
   if(itemset[i].index==index){
    item = itemset[i];
    break;
   }
  }
  return item;
 }
 
 /**
  * Calculates and returns the summation of list of item weights
  */
 this.getWeightForList = function(itemset){
  var sum = 0;
  for(var i=0;i<itemset.length;i++){
   sum += itemset[i].weight;
  }
  return sum;
 }
 
 /**
  * Calculates and returns the summation of list of item values
  */
 this.getValueForList = function(itemset){
  var sum = 0;
  for(var i=0;i<itemset.length;i++){
   sum += itemset[i].value;
  }
  return sum;
 }
 
 /**
  * Checks whether current selection is overweight or not
  */
 this.checkoverweight = function(itemset){
  if(this.getWeightForList(itemset) > this.size){
   return true;
  }else
   return false;
 }
 
 /**
  * Returns any random item from the itemset which is not in the currentSolution of the bag
  */
 this.getRandomItemFromItemSet = function(){
  var temp = getRandomAsInt(0,this.itemset.length);
  var item  = this.getItemBasedOnIndex(this.itemset,temp);
  while(this.getItemBasedOnIndex(this.currentSolution,temp)!=null){
   temp = getRandomAsInt(0,this.itemset.length);
   item  = this.getItemBasedOnIndex(this.itemset,temp);
  }
  return item;
 }
 
 /**
  * Modifies the current selection
  */
 this.modifySelection = function(){
  var modified = this.currentSolution.clone();
  var item = this.getRandomItemFromItemSet();
  modified.push(item);
  while(this.checkoverweight(modified)){
   var dropIndex = getRandomAsInt(0,modified.length);
   modified.removeItem(dropIndex);
   console.log(dropIndex);
   console.log(modified);
      
  }
  return modified;
 }
 
 /**
  * Calculates the remaining space in the bag
  */
 this.calculateRemainingSpace = function(itemset){
  return (this.size - this.getValueForList(itemset));
 }
 
 this.printsolution = function(itemset){
  for(var i=0;i<itemset.length;i++){
   var item = itemset[i];
   item.print();
  }
  document.write("Total value is : "+this.getValueForList(itemset));
 }
 
 this.prepare();
}

/**
 * Returns a random number between minimum (inclusive) and maximum (exclusive)
 */
function getRandom(min, max) {
    return Math.random() * (max - min) + min;
}

/**
 * Returns a random integer between minimum (inclusive) and maximum (exclusive)
 */
function getRandomAsInt(min, max) {
    return Math.floor(Math.random() * (max - min)) + min;
}

Array.prototype.clone = function() {
 return this.slice(0);
};

Array.prototype.removeItem = function( index){
    var i = 0;
    while( i < this.length ){
     if(i == index ){
      this.splice(i,1);
     }
     i++;
    }
};

index.html

<script src="knapsack.js"></script>
<script>
/**
 * Constants for the program
 */
var MAX_WEIGHT = 15;
var TEMPERATURE = 500;
var COOLING_FACTOR = 0.2;

/**
 * The dataset used in the program
 * [weight,value]
 */
var dataset = [
                [1,2],[4,2],[5,4],[3,6],[9,4],[10,8],[8,5],[6,7],[7,3],[11,8]
               ];

/** Acceptance function **/
function acceptanceProbability(freespace,newfreespace,temperature){
 if(newfreespace < freespace){
  return 1.0;
 }
 return Math.exp((freespace - newfreespace) / temperature);
}


window.onload = function(){
 var bag = new Bag(MAX_WEIGHT);
 var best = bag.currentSolution;
 var temperature = TEMPERATURE;
 while(temperature > 0){
  var freespaceLeft = bag.calculateRemainingSpace(bag.currentSolution);
  var modifiedSolution = bag.modifySelection();
  var newfreespaceleft = bag.calculateRemainingSpace(modifiedSolution);
  if(acceptanceProbability(freespaceLeft, newfreespaceleft, temperature)>=Math.random()){
   bag.currentSolution = modifiedSolution;
  }
  
  if(bag.getValueForList(bag.currentSolution) > bag.getValueForList(best)){
   best = bag.currentSolution;
  }
  temperature -= COOLING_FACTOR;
 }
 bag.printsolution(best);
}
</script>