Data Structures, Algorithms, & Applications in Java
Chapter 18, Exercise 17

(a)

The profit densities are [0.2, 1.5, 1.5]. Therefore we consider the objects in the order 2, 3, 1. Objects 2 and 3 are packed and then 0.85 of object 2 is packed. The solution is x = [0.85, 1, 1] and the profit earned from the packing is 47.

(b)

Consider any instance of the continuous knapsack problem. We may assume that the objects are given in nonincreasing order of profit density. Let x1 ... xn be the greedy solution and let y1 ... yn be an optimal solution. We shall show that both solutions earn the same profit and so the greedy solution is also optimal.

Let j be the least integer such that xi = yi, 1 <= i < j and xj != yj. If no such j exists, the two solutions are the same and so the greedy solution is optimal. Assume such a j exists. From the way the greedy algorithm works and the fact that the optimal solution is a feasible solution, we conclude that xj > yj. If we increase the fraction of object j in the optimal solution to xj and reduce the fraction of objects j+1, j+2, ... to compensate for the increased weight used by object j, the profit cannot decrease because we are replacing lower density fractions by higher or equal density ones. This transformation, therefore, yields a new optimal solution for which the least integer j such that xi = yi, 1 <= i < j and xj != yj (if it exists) is larger than for the old optimal solution.

By applying this transformation a finite number of times, we convert the original optimal solution into the greedy solution without decreasing the profit earned. So the greedy solution must also be optimal.

(c)

We shall assume that the profits and weights are of type double. First we define a class Element which is used to sort the objects into nondecreasing order of profit density. Following the sort, the objects are to be packed into the knapsack in the reverse of this order.

The method gerredyKnapsack packs the objects into the knapsack in nonincreasing order of profit density. It returns the profit generated by the greedy packing. It also sets x[i] to be the fraction of object i that is packed into the knapsack.

---

public class ContinuousKnapsack
{
   static class Element implements Comparable
   {
      // data members
      int id;   // object identifier
      double d; // profit density

      // constructor
      private Element(int theID, double theDensity)
      {
         id = theID;
         d = theDensity;
      }

     // method of Comparable
     /** return true iff this < x */
     public int compareTo(Object x)
     {
        double xD = ((Element) x).d;
        if (d < xD)
           return -1;
        if (d == xD)
           return 0;
        return 1;
      }
  
      /** return true iff this == x */
      public boolean equals(Object x)
         {return d == ((Element) x).d;}
   }

   /** set x[i] to the fraction of object i included in knapsack,
     * 1 <= i < p.length
     * param p[1:p.length-1] array of profits
     * param w[1:w.length-1] array of weights
     * param c knapsack capacity
     * return value of greedy knapsack filling */
   public static double greedyContinuousKnapsack(double [] p,
                              double [] w, double c, float [] x)
   {
      // define an element array to be sorted by profit density
      Element [] q = new Element [p.length];
      for (int i = 1; i < p.length; i++)
         // array of profit densities
         q[i] = new Element(i, p[i] / w[i]);
   
      // sort by density
      HeapSort.heapSort(q);
   
      // load in nonincreasing order of density and compute profit sum
      double profitSum = 0;      // will be sum of profits
      int i;
      for (i = p.length - 1; i > 0; i--)
      {
         int id = q[i].id;
         if (w[id] <= c )
         {// object id fits
            x[id] = 1;
            c -= w[id];
            profitSum += p[id];
         }
         else
         {// object id is too large
          // take a fraction of this object to fill knapsack
            x[id] = (float) (c / w[id]);
            profitSum += x[id] * p[id];
            break;
         }
      }
   
      // set remaining x[] values to zero
      for (int j = i - 1; j > 0; j--)
         x[q[j].id] = 0;

      return profitSum;
   }
}

The above code together with test data and output appear in the files ContinuousKnapsack.*.

Since the knapsack will usually get filled after the first few items have been examined, we can avoid doing a total sort as is done above. Instead, we can start by setting all x[i] to zero and initializing a max heap with the objects. Then objects are extracted from the max heap one by one and packed into the knapsack until the knapsack is full. Since a max heap can be initialized in linear time, the complexity of the new knapsack algorithm is O(n + k log n), where k is the number of objects extracted from the max heap. In the worst case, k = n and the complexity becomes the same as when we started by sorting the objects.