Knapsack problem/0-1

Knapsack problem/0-1
You are encouraged to solve this task according to the task description, using any language you may know.

See also: Knapsack problem

A tourist wants to make a good trip at the weekend with his friends. They will go to the mountains to see the wonders of nature. So he needs some items during the trip. Food, clothing, etc. He has a good knapsack for carrying the things, but he knows that he can carry only 4 kg weight in his knapsack, because they will make the trip from morning to evening. He creates a list of what he wants to bring for the trip, but the total weight of all items is too much. He adds a value to each item. The value represets how important the thing for the tourist.

This is the list:

Item	Weight (dkg)	Value
map	9	150
compass	13	35
water	153	200
sandwich	50	160
glucose	15	60
tin	68	45
banana	27	60
apple	39	40
cheese	23	30
beer	52	10
suntan cream	11	70
camera	32	30
t-shirt	24	15
trousers	48	10
umbrella	73	40
waterproof trousers	42	70
waterproof overclothes	43	75
note-case	22	80
sunglasses	7	20
towel	18	12
socks	4	50
book	30	10
Knapsack	<=400 dkg	?

He can only take whole units of any item, and he has only one piece from the items.

Which items he has to carry in his knapsack that the weight of knapsack does not have to exceed the 4 kg maximal weight, and the total value has to be maximal?

Java

General dynamic solution after wikipedia.

<lang java> package hu.pj.alg.test;

import hu.pj.alg.ZeroOneKnapsack; import hu.pj.obj.Item; import java.util.*; import java.text.*;

public class ZeroOneKnapsackForTurists {

   public ZeroOneKnapsackForTurists() {
       ZeroOneKnapsack zok = new ZeroOneKnapsack(400); // 400 dkg = 4kg

       // making the list of items that you want to bring
       zok.add("map", 9, 150);
       zok.add("compass", 13, 35);
       zok.add("water", 153, 200);
       zok.add("sandwich", 50, 160);
       zok.add("glucose", 15, 60);
       zok.add("tin", 68, 45);
       zok.add("banana", 27, 60);
       zok.add("apple", 39, 40);
       zok.add("cheese", 23, 30);
       zok.add("beer", 52, 10);
       zok.add("suntan cream", 11, 70);
       zok.add("camera", 32, 30);
       zok.add("t-shirt", 24, 15);
       zok.add("trousers", 48, 10);
       zok.add("umbrella", 73, 40);
       zok.add("waterproof trousers", 42, 70);
       zok.add("waterproof overclothes", 43, 75);
       zok.add("note-case", 22, 80);
       zok.add("sunglasses", 7, 20);
       zok.add("towel", 18, 12);
       zok.add("socks", 4, 50);
       zok.add("book", 30, 10);

       // calculate the solution:
       List<Item> itemList = zok.calcSolution();

       // write out the solution in the standard output
       if (zok.isCalculated()) {
           NumberFormat nf  = NumberFormat.getInstance();

           System.out.println(
               "Maximal weight           = " +
               nf.format(zok.getMaxWeight() / 100.0) + " kg"
           );
           System.out.println(
               "Total weight of solution = " +
               nf.format(zok.getSolutionWeight() / 100.0) + " kg"
           );
           System.out.println(
               "Total value              = " +
               zok.getProfit()
           );
           System.out.println();
           System.out.println(
               "You can carry te following materials " +
               "in the knapsack:"
           );
           for (Item item : itemList) {
               if (item.isInKnapsack()) {
                   System.out.format(
                       "%1$-23s %2$-3s %3$-5s %4$-15s \n",
                       item.getName(),
                       item.getWeight(), "dkg  ",
                       "(value = " + item.getValue() + ")"
                   );
               }
           }
       } else {
           System.out.println(
               "The problem is not solved. " +
               "Maybe you gave wrong data."
           );
       }

   }

   public static void main(String[] args) {
       new ZeroOneKnapsackForTurists();
   }

} </lang>

<lang java> package hu.pj.alg;

import hu.pj.obj.Item; import java.util.*;

public class ZeroOneKnapsack {

   private List<Item> itemList = new ArrayList<Item>();
   protected int maxWeight         = 0;
   protected int solutionWeight    = 0;
   protected int profit            = 0;
   protected boolean calculated    = false;
   
   public ZeroOneKnapsack() {}
   
   public ZeroOneKnapsack(int _maxWeight) {
       setMaxWeight(_maxWeight);
   }

   public ZeroOneKnapsack(List<Item> _itemList) {
       setItemList(_itemList);
   }

   public ZeroOneKnapsack(List<Item> _itemList, int _maxWeight) {
       setItemList(_itemList);
       setMaxWeight(_maxWeight);
   }

   // calculte the solution of 0-1 knapsack problem with dynamic method:
   public List<Item> calcSolution() {
       int n = itemList.size();

       setInitialStateForCalculation();
       if (n > 0  &&  maxWeight > 0) {
           List< List<Integer> > c = new ArrayList< List<Integer> >();
           List<Integer> curr = new ArrayList<Integer>();

           c.add(curr);
           for (int j = 0; j <= maxWeight; j++)
               curr.add(0);
           for (int i = 1; i <= n; i++) {
               List<Integer> prev = curr;
               c.add(curr = new ArrayList<Integer>());
               for (int j = 0; j <= maxWeight; j++) {
                   if (j > 0) {
                       int wH = itemList.get(i-1).getWeight();
                       curr.add(
                           (wH > j)
                           ?
                           prev.get(j)
                           :
                           Math.max(
                               prev.get(j),
                               itemList.get(i-1).getValue() + prev.get(j-wH)
                           )
                       );
                   } else {
                       curr.add(0);
                   }
               } // for (j...)
           } // for (i...)
           profit = curr.get(maxWeight);

           int j = maxWeight;
           for (int i = n; i > 0 && j >= 0; i--) {
               int tempI   = c.get(i).get(j);
               int tempI_1 = c.get(i-1).get(j);
               if (
                   (i == 0  &&  tempI > 0)
                   ||
                   (i > 0  &&  tempI != tempI_1)
               )
               {
                   Item iH = itemList.get(i-1);
                   int  wH = iH.getWeight();
                   iH.setInKnapsack(true);
                   j -= wH;
                   solutionWeight += wH;
               }
           } // for()
           calculated = true;
       } // if()
       return itemList;
   }

   // add an item to the item list
   public void add(String name, int weight, int value) {
       if (name.equals(""))
           name = "" + (itemList.size() + 1);
       itemList.add(new Item(name, weight, value));
       setInitialStateForCalculation();
   }

   // add an item to the item list
   public void add(int weight, int value) {
       add("", weight, value); // the name will be "itemList.size() + 1"!
   }

   // remove an item from the item list
   public void remove(String name) {
       for (Iterator<Item> it = itemList.iterator(); it.hasNext(); ) {
           if (name.equals(it.next().getName())) {
               it.remove();
           }
       }
       setInitialStateForCalculation();
   }

   // remove all items from the item list
   public void removeAllItems() {
       itemList.clear();
       setInitialStateForCalculation();
   }

   public int getProfit() {
       if (!calculated)
           calcSolution();
       return profit;
   }

   public int getSolutionWeight() {return solutionWeight;}
   public boolean isCalculated() {return calculated;}
   public int getMaxWeight() {return maxWeight;}

   public void setMaxWeight(int _maxWeight) {
       maxWeight = Math.max(_maxWeight, 0);
   }

   public void setItemList(List<Item> _itemList) {
       if (_itemList != null) {
           itemList = _itemList;
           setInKnapsackByAll(false);
       }
   }

   // set the member with name "inKnapsack" by all items:
   private void setInKnapsackByAll(boolean inKnapsack) {
       for (Item item : itemList)
           item.setInKnapsack(inKnapsack);
   }

   // set the data members of class in the state of starting the calculation:
   protected void setInitialStateForCalculation() {
       setInKnapsackByAll(false);
       calculated     = false;
       profit         = 0;
       solutionWeight = 0;
   }

} // class </lang>

<lang java> package hu.pj.obj;

public class Item {

   protected String name = "";
   protected int weight = 0;
   protected int value = 0;
   protected boolean inKnapsack = false;

   public Item() {}

   public Item(Item item) {
       setName(item.name);
       setWeight(item.weight);
       setValue(item.value);
   }

   public Item(int _weight, int _value) {
       setWeight(_weight);
       setValue(_value);
   }

   public Item(String _name, int _weight, int _value) {
       setName(_name);
       setWeight(_weight);
       setValue(_value);
   }

   public void setName(String _name) {name = _name;}
   public void setWeight(int _weight) {weight = Math.max(_weight, 0);}
   public void setValue(int _value) {value = Math.max(_value, 0);}
   public void setInKnapsack(boolean inKnaps) {inKnapsack = inKnaps;}

   public String getName() {return name;}
   public int getWeight() {return weight;}
   public int getValue() {return value;}
   public boolean isInKnapsack() {return inKnapsack;}

} // class </lang>

output:

Maximal weight           = 4 kg
Total weight of solution = 3,96 kg
Total value              = 1030

You can carry te following materials in the knapsack:
map                     9   dkg   (value = 150)   
compass                 13  dkg   (value = 35)    
water                   153 dkg   (value = 200)   
sandwich                50  dkg   (value = 160)   
glucose                 15  dkg   (value = 60)    
banana                  27  dkg   (value = 60)    
suntan cream            11  dkg   (value = 70)    
waterproof trousers     42  dkg   (value = 70)    
waterproof overclothes  43  dkg   (value = 75)    
note-case               22  dkg   (value = 80)    
sunglasses              7   dkg   (value = 20)    
socks                   4   dkg   (value = 50)    

Tcl

As the saying goes, “when in doubt, try brute force”. Since there's only 22 items we can simply iterate over all possible choices. <lang tcl># The list of items to consider, as list of lists set items {

   {map			9	150}
   {compass			13	35}
   {water			153	200}
   {sandwich			50	160}
   {glucose			15	60}
   {tin			68	45}
   {banana			27	60}
   {apple			39	40}
   {cheese			23	30}
   {beer			52	10}
   {{suntan cream}		11	70}
   {camera			32	30}
   {t-shirt			24	15}
   {trousers			48	10}
   {umbrella			73	40}
   {{waterproof trousers}	42	70}
   {{waterproof overclothes}	43	75}
   {note-case			22	80}
   {sunglasses			7	20}
   {towel			18	12}
   {socks			4	50}
   {book			30	10}

}

1. Simple extraction functions

proc names {chosen} {

   set names {}
   foreach item $chosen {lappend names [lindex $item 0]}
   return $names

} proc weight {chosen} {

   set weight 0
   foreach item $chosen {incr weight [lindex $item 1]}
   return $weight

} proc value {chosen} {

   set value 0
   foreach item $chosen {incr value [lindex $item 2]}
   return $value

}

1. Recursive function for searching over all possible choices of items

proc knapsackSearch {items {chosen {}}} {

   # If we've gone over the weight limit, stop now
   if {[weight $chosen] > 400} {

return

   }
   # If we've considered all of the items (i.e., leaf in search tree)
   # then see if we've got a new best choice.
   if {[llength $items] == 0} {

global best max set v [value $chosen] if {$v > $max} { set max $v set best $chosen } return

   }
   # Branch, so recurse for chosing the current item or not
   set this [lindex $items 0]
   set rest [lrange $items 1 end]
   knapsackSearch $rest $chosen
   knapsackSearch $rest [lappend chosen $this]

}

1. Initialize a few global variables

set best {} set max 0

1. Do the brute-force search

knapsackSearch $items

1. Pretty-print the results

puts "Best filling has weight of [weight $best]hg and score [value $best]" puts "Best items:\n\t[join [lsort [names $best]] \n\t]"</lang> Output:

Best filling has weight of 396hg and score 1030
Best items:
	banana
	compass
	glucose
	map
	note-case
	sandwich
	socks
	sunglasses
	suntan cream
	water
	waterproof overclothes
	waterproof trousers