Knapsack problem

knapsack.java

// "static void main" must be defined in a public class.
public class Knapsack {
    
    private String[] name;
    private int[] weight;
    private int[] value;
    private int[][] m;
    private int capacity;
    
    public static void main(String[] args) {
        int n = 8;
        int capacity = 30;
        Knapsack k = new Knapsack();
        k.randomInit(n,capacity);
        k.weight = new int[]{10, 11, 7, 12, 12, 6, 10, 3};
        k.value = new int[]{8, 5, 5, 29, 6, 4, 27, 1};
        System.out.println("items:"+Arrays.toString(k.name));
        System.out.println("weight:"+Arrays.toString(k.weight));
        System.out.println("value:"+Arrays.toString(k.value));

        System.out.println("max:"+k.calc(n,capacity));
        
        int[] selected = k.findSelected(n,capacity);
        System.out.println("\nRecursive result:");
        k.printSelected(selected);
        
        selected = k.scanAll();
        System.out.println("\nScan all result:");
        k.printSelected(selected);

    }
    
    public int calc(int i, int w) {
        if (m[i][w]<0) {
            if (i==0) {
                m[i][w] = 0;
            } else {
                //"weight" and "value" array is zero base
                if (weight[i-1] > w) { 
                    m[i][w] = calc(i-1,w);
                } else {
                    m[i][w] = Math.max(calc(i-1,w),calc(i-1,w-weight[i-1])+value[i-1]);
                }
            }
        }
        return m[i][w];
    }
    
    public int[] findSelected(int i, int w) {
        if (i==0) {
            return new int[0];
        } else {
            if (m[i][w] > m[i-1][w]) {
                int[] items = findSelected(i-1,w-weight[i-1]);
                items = Arrays.copyOf(items,items.length+1);
                items[items.length-1] = i;
                return items;
            } else {
                return findSelected(i-1,w);
            }
        }
    }

    public int[] scanAll() {
        int n = weight.length;
        List<Integer> best = new ArrayList<Integer>();
        List<Integer> set = new ArrayList<Integer>();
        int maxValue=0;
        for (int c=1;c<Math.pow(2,n);c++) {
            set.clear();
            int ttlValue = 0;
            int ttlWeight = 0;
            for (int i=0;i<n;i++) {
                if (((c>>i)&1)==1) {
                    set.add(i+1);
                    ttlValue += value[i];
                    ttlWeight += weight[i];
                }
            }
            if (ttlWeight<=capacity) {
                if (ttlValue > maxValue) {
                    maxValue = ttlValue;
                    best.clear();
                    best.addAll(set);
                }
            }
        }
        int[] selected = new int[best.size()];
        for (int i=0;i<selected.length;i++) {
            selected[i] = best.get(i);
        }
        return selected;
    }
    
    public void randomInit(int n, int c) {
        Random rand = new Random();
        capacity = c;
        name = new String[n];
        weight = new int[n];
        value = new int[n];
        m = new int[n+1][c+1];
        for (int i=0;i<m.length;i++) {
            for (int j=0;j<m[i].length;j++) {
                m[i][j] =-1;
            }
        }
        
        for (int i=0;i<n;i++) {
            name[i] = ""+(char)((int)'A'+i);
            weight[i] = rand.nextInt(c/3)+3;
            value[i] = rand.nextInt(29)+1;
        }
    }
    
    public void printSelected(int[] selected) {
        System.out.println("selected items:");
        int ttlWeight = 0, ttlValue = 0;
        for (int i:selected) {
            ttlWeight += weight[i-1];
            ttlValue += value[i-1];
            System.out.println(name[i-1]+",w:"+weight[i-1]+",v:"+value[i-1]);
        }
        System.out.println("ttl - w:"+ttlWeight+"/"+capacity+",v:"+ttlValue);        
    }
}