

A thief burgles a butcher's shop, where he can select from some items.

The thief knows the weights and prices of each items.   Because he has a knapsack with 15 kg maximal capacity, he wants to select the items such that he would have his profit maximized.   He may cut the items;   the item has a reduced price after cutting that is proportional to the original price by the ratio of masses.   That means:   half of an item has half the price of the original.



This is the item list in the butcher's shop:


 Table of potential knapsack items


 Item 
 Weight (kg) 
 Price (Value)


 beef 
 3.8 
 36


 pork 
 5.4 
 43


 ham 
 3.6 
 90


 greaves 
 2.4 
 45


 flitch 
 4.0 
 30


 brawn 
 2.5 
 56


 welt 
 3.7 
 67


 salami 
 3.0 
 95


 sausage 
 5.9 
 98


 Knapsack 
 <=15 kg 
 ?



Task

Show which items the thief carries in his knapsack so that their total weight does not exceed 15 kg, and their total value is maximized.



Related tasks

   Knapsack problem/Bounded
   Knapsack problem/Unbounded
   Knapsack problem/0-1


See also

   Wikipedia article:   continuous knapsack.


 
package hu.pj.alg.test;
 
import hu.pj.alg.ContinuousKnapsack;
import hu.pj.obj.Item;
import java.util.*;
import java.text.*;
 
public class ContinousKnapsackForRobber {
    final private double tolerance = 0.0005;
 
    public ContinousKnapsackForRobber() {
        ContinuousKnapsack cok = new ContinuousKnapsack(15); // 15 kg
 
        // making the list of items that you want to bring
        cok.add("beef",     3.8, 36); // marhahús
        cok.add("pork",     5.4, 43); // disznóhús
        cok.add("ham",      3.6, 90); // sonka
        cok.add("greaves",  2.4, 45); // tepertő
        cok.add("flitch",   4.0, 30); // oldalas
        cok.add("brawn",    2.5, 56); // disznósajt
        cok.add("welt",     3.7, 67); // hurka
        cok.add("salami",   3.0, 95); // szalámi
        cok.add("sausage",  5.9, 98); // kolbász
 
        // calculate the solution:
        List<Item> itemList = cok.calcSolution();
 
        // write out the solution in the standard output
        if (cok.isCalculated()) {
            NumberFormat nf  = NumberFormat.getInstance();
 
            System.out.println(
                "Maximal weight           = " +
                nf.format(cok.getMaxWeight()) + " kg"
            );
            System.out.println(
                "Total weight of solution = " +
                nf.format(cok.getSolutionWeight()) + " kg"
            );
            System.out.println(
                "Total value (profit)     = " +
                nf.format(cok.getProfit())
            );
            System.out.println();
            System.out.println(
                "You can carry the following materials " +
                "in the knapsack:"
            );
            for (Item item : itemList) {
                if (item.getInKnapsack() > tolerance) {
                    System.out.format(
                        "%1$-10s %2$-15s %3$-15s \n",
                        nf.format(item.getInKnapsack()) + " kg ",
                        item.getName(),
                        "(value = " + nf.format(item.getInKnapsack() *
                                                (item.getValue() / item.getWeight())) + ")"
                    );
                }
            }
        } else {
            System.out.println(
                "The problem is not solved. " +
                "Maybe you gave wrong data."
            );
        }
 
    }
 
    public static void main(String[] args) {
        new ContinousKnapsackForRobber();
    }
 
} // class