Fractional knapsack problem

Fractional knapsack problem is a variation of original 0-1 Knapsack problem.

In the original problem we are not allowed to break items. We either take the whole item or don’t take it. But in this we can break the items into fraction and use to get the maximum value.

The problem statement reads like this, Given a list of items, each having associated weight and a value, we need to put these items in a knapsack of capacity W to get the maximum total value in the knapsack. You are allowed to break the items if required.

Example

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;

Output:
//Bounded 
18.4
By taking whole items of weight 4, 2, 1, 2 and 0.6% of 10kg. 
Hence total price will be 12 + 2 + 1 + 2 + (0.6)(4) = 17 + 2.4 = 18.4

//Unbounded
45
By taking item with max ratio (12/4) = 3 repeatedly for the given capacity
3 * 15 = 45

Bounded Fractional knapsack problem in Javascript

The knapsack problem is in combinatorial optimization problem and can be solved using greedy approach.

Conceptually this is how it will work.

• For each item, calculate the ratio value/weight for each item and sort the item on basis of this ratio.
• Then take the item with the highest ratio and add them until we can’t add the next item as a whole and at the end add the next item in fractions as much as we can .
• Which will always be the optimal solution to this problem.

To calculate the ratio we will use an extra object and then sort the array of these object based on the ratio in descending order.

//Object to store item value
const ItemValue = function(wt, val) {
  this.wt = wt; 
  this.val = val; 
  this.ratio = val / wt;
}

const getMaxValue = (wt, val, capacity) => {
  //Create a new temp array
  let iVal = new Array(wt.length);
  
  //Store each item along with its weight
  for (let i = 0; i < wt.length; i++) { 
    iVal[i] = new ItemValue(wt[i], val[i]); 
  } 
  
   // sorting items by value in descending order; 
   iVal = iVal.sort((a, b) => b.ratio - a.ratio);
    
   //Store the result
   let totalValue = 0;
   
   //Iterate all the item values
   for (let i of iVal) { 
     let curWt = i.wt; 
     let curVal = i.val; 

     if (capacity - curWt >= 0) { 
       // this weight can be picked while 
       capacity = capacity - curWt; 
       totalValue += curVal; 
     } 
     else { 
       // item cant be picked whole 
       let fraction = (capacity / curWt); 
       totalValue += (curVal * fraction); 
       capacity = (capacity - (curWt * fraction)); 
       break; 
     } 
   } 

  return totalValue;
}

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;
console.log(getMaxValue(weights, values, capacity));

Output:
18.4

Time complexity: O(nlogn).
Space complexity: O(n).

---

Unbounded fractional knapsack in Javascript

In the unbounded, get the max ratio of any given item and fill the bag with that items only to the get the max value.

// function to return the maximum required value
const unboundedFractionalKnapsack = (val, wt, n, W) => {
   // stores the max value/weight ratio
   let maxratio = Number.MIN_VALUE;
   
   // find the maximum ratio
   for (let i = 0; i < n; i++) {
     const ratio = (val[i] / wt[i]); 
     if ( ratio > maxratio) {
       maxratio = ratio;
     }
   }

   // add the item with max ratio in the bag
   // till the bag is full
   return (W * maxratio);
 }

Input:
const values = [12, 2, 1, 4, 1];
const weights = [4, 2, 1, 10, 2];
const target = 15;

console.log(unboundedFractionalKnapsack(values, weights, values.length - 1, target));

Output:
45

Time complexity: O(n).
Space complexity: O(1).