01Knapsack in php

<?php
/* PHP is pass by value semantics.
   To pass by reference one uses the $& symbol for the
   parameters.
   Take the array of weights and array of benefits/value and
   try to infer the best possible combination for value M.
 */
    $b = array(50, 40, 30, 10);
    $w = array(3,   4,  6,  5);
    $b1 = array(4,   3,  6,  5);
    $w1 = array(3,   2,  5,  4);
    
    function listItems(array & $B, $n, $M)
    {
       $i = $n;
       $j = $M;  
       global $w, $b;
       $maxb = 0;
      
       while ($i > 0 && $j > 0)
       {
          if ($B[$i][$j] !=  $B[$i-1][$j])
          {
            print ("Take item number: $i ");
            echo "<BR/>\n";           
           
            $j = $j - $w[$i-1];
            $i = $i - 1;
            $maxb += $b[$i];
          }
          else 
            $i = $i - 1;
       }
       print ("Max benefit: $maxb ");
       echo "<BR/>\n";           
    }
   
    function printTable(array & $B, & $n, & $M)
    {
       $maxv = 0;
      
       $mw = 0;
       $mb = 0;
      
       for ($i = 0 ; $i <= $n; $i++)
       {
         for ($j = 0 ; $j <= $M; $j++)
         {
            printf("%02d ", $B[$i][$j]);
            if ($maxv < $B[$i][$j])
            {
               $mw = $i;
               $mb = $j;
               $maxv = $B[$i][$j];
            }           
         }
         echo "<BR/>\n";
       }
       echo "<BR/>\n";
      
       # Set the index where maximum exists
       $n = $mw;
       $M = $mb;
       printf("%02d \n", $B[$n][$M]); echo "<BR/>\n";
    }
   
    function knapsack01 (array & $w, array & $b, $M)
    {
        /* Two dimensional array to pre-compute */
        $B = array(array());
        $n = count($w);
       
        for ($indx = 0; $indx <= $n ; $indx++)
           $B[$indx][0] = 0;
  
        for ($indx = 0; $indx <= $M ; $indx++)
           $B[0][$indx] = 0;
      
        for ($i = 1; $i <= $n ; $i++)
        {
           for ($j = 0; $j <= $M ; $j++)
           {
              if ($w[$i-1] <= $j &&
                  ($B[$i-1][$j-$w[$i-1]] + $b[$i-1]) > $B[$i-1][$w[$i-1]])
              {
                 $B[$i][$j] = $B[$i-1][$j-$w[$i-1]] + $b[$i-1];             
              }
              else
                 $B[$i][$j] = $B[$i-1][$j];
           }
        }
        printTable ($B, $n, $M);
        listItems  ($B, $n, $M);
    }
   
    knapsack01 ($w, $b, 9);
?>

01 Knapsack in Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class KnapSack01 {
 
  List b = Arrays.asList(10, 40, 30, 50);
  List w = Arrays.asList(5, 4, 6, 3);
  private int B[][];
 
  public int getNum() { return w.size(); }
 
  public KnapSack01(int M)
  {
    doAlloc(w.size()+1, M+1);
    doAllot(w.size(), M+1);
    printTable(w.size()+1, M+1);
  }
 
  public static void main(String args[])
  {
    KnapSack01 ks = new KnapSack01(10);    
   
    ks.listItems(10);
  }
 
  public void listItems(int M)
  {
    int i = getNum();
    int k = M;
   
    while (i > 0 && k >0)
    {
      if (B[i][k] != B[i-1][k])
      {
        System.out.println(i + " is in the knapsack");
        i = i - 1;
        k = k - (int)w.get(i-1);
      }
      else
        i = i - 1;
    }
  }
 
  public void printTable(int n, int M)
  {
    for (int i = 0 ; i < n; i++)
    {
      for (int j = 0 ; j < M; j++)
        System.out.printf("%02d ", B[i][j]);
      System.out.println();
    }
  }
 
  public void doAlloc(int n, int M)
  {
    B  = new int[n][M];
   
    for (int i = 0 ; i < n; i++)
      B[i][0] = 0;
    for (int j = 0 ; j < M; j++)
      B[0][j] = 0;   
  }
 
  public void doAllot(int n, int M)
  {
    for (int i = 1 ; i <= n; i++)
    {
      for (int j = 0 ; j < M; j++) 
      {
        if ((int)w.get(i-1) <= j &&
            (((int)b.get(i-1) + B[i-1][j-(int)w.get(i-1)]) > B[i-1][(int)w.get(i-1)]))
        {
          B[i][j] = (int)b.get(i-1) + B[i-1][j-(int)w.get(i-1)];           
        }
        else
          B[i][j] = B[i-1][j];
      }     
    }
  }
}