IntegerKnapsackSolver.java

package arrayexperiment;

import org.apache.commons.lang.ArrayUtils;

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

/**
 * Created with IntelliJ IDEA.
 * Author: Edouard
 */
public class IntegerKnapsackSolver {

    private final int target;
    private final int[] steps;

    private List<Integer> solution = null;
    private final HashMap<Integer, List<Integer>> memoize;

    public IntegerKnapsackSolver(int N, int[] steps) {
        this.target = N;
        this.steps = Arrays.copyOf(steps, steps.length);
        Arrays.sort(this.steps);
        ArrayUtils.reverse(this.steps);
        this.memoize = new HashMap<Integer, List<Integer>>(N);
    }

    public boolean isSolved() {
        return this.solution != null;
    }

    public List<Integer> solve() {
        if (!isSolved()) {
            this.solution = solveForN(target);
        }
        return this.solution;
    }

    private List<Integer> solveForN(int N) {
        if (N == 0) {
            return new ArrayList<Integer>();
        } else if (N > 0) {
            if (!this.memoize.containsKey(N)) {
                List<Integer> temp, min = null;
                for (int i = 0; i < steps.length; i++) {
                    temp = solveForN(N - steps[i]);
                    if (temp != null) {
                        temp.add(steps[i]);
                        if (min == null || min.size() > temp.size()) {
                            min = temp;
                        }
                    }
                }
                if (min != null) {
                    this.memoize.put(N, new ArrayList<Integer>(min));
                }
                return min;
            } else {
                return this.memoize.get(N);
            }
        } else {
            return null;
        }
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("IntegerKnapsackSolver{");
        sb.append("target=").append(target);
        sb.append(", steps=").append(Arrays.toString(steps));
        sb.append(", solution=").append(solution);
        if (memoize.size() < 20) {
            sb.append(", memoize=").append(memoize);
        }
        sb.append('}');
        return sb.toString();
    }
}