IntegerKnapsack.java

import java.util.HashMap;
/*
The Integer Knapsack Problem (Duplicate Items Permitted). You have n types of
items, where the ith item type has an integer size si and a real value vi. You are trying to fill a knapsack of
total capacity C with a selection of items of maximum value. You can add multiple items of the same type
to the knapsack.
 
s = {3,1,2,4}
v = {4,1,3,2}
 
item1: has size 3 and value 4
item2
3 
4
 
bag, capacity c = 7
one way is:
put item1 and item 4 in the bag (3+4<=7), the value is 4+2=6 
 
*/
 
public class IntegerKnapsack {
 
    public static int getMaxValue(int[] s, int[] v, int c) {
        HashMap<Integer, Integer> sm = new HashMap<Integer, Integer>();
        for (int i=0; i<s.length; i++) {
            if (sm.containsKey(v[i]) && sm.get(v[i]) < s[i]) {
                continue;
            }
            sm.put(v[i], s[i]);
        }
        Arrays.sort(v);
        int max = 0;
        int i = v.length - 1;
        while (i >= 0 && c > 0) {
            int si = sm.get(v[i]);
            if (si > c) {
                 //Use the next lesser element only if the capacity exceeds
                i--;
                continue;
            }
            max += v[i];
            c -= si;
        }
        return max;
    }
 
    public static void main(String[] args) {
        int[] s = {5, 21, 12, 7, 15, 13};
        int[] i = {6, 3, 9, 9, 4, 2};
        System.out.println(IntegerKnapsack.getMaxValue(s, i, 15));
    }
}