Java Code Examples: Backpack & Maximum Subarray

Posted on Feb 8, 2025 in Computer Engineering

Backpack Problem Implementation in Java

This code implements a solution to the Backpack problem using a depth-first search approach. The Alforja class represents the backpack and its contents.

public class Alforja implements Solution {
    private ArrayList<Integer> pesos;
    private ArrayList<Integer> valors;
    private ArrayList<Integer> alforja;
    public static int MAXPES = 0;

    public Alforja() {
        pesos = new ArrayList<>();
        valors = new ArrayList&lt;>();
        alforja = new ArrayList<>();
    }

    public void setPesos(ArrayList<Integer> llistapesos) {
        pesos = llistapesos;
    }

    public void setValors(ArrayList<Integer> llistavalors) {
        valors = llistavalors;
    }

    public int getObjective() {
        int objectiu = 0;
        for (int i = 0; i < alforja.size(); i++) {
            objectiu += valors.get(i) * alforja.get(i);
        }
        return Integer.MAX_VALUE - objectiu;
    }

    public boolean isComplete() {
        return (pesos.size() == alforja.size());
    }

    public boolean isFeasible() {
        double pes = 0;
        for (int i = 0; i < alforja.size(); i++) {
            pes += pesos.get(i) * alforja.get(i);
        }
        if (pes <= MAXPES)
            return true;
        else
            return false;
    }

    public Iterator getSuccessors() {
        ArrayList<Alforja> llistaAux = new ArrayList<>();
        Alforja copia;
        try {
            copia = (Alforja) this.clone();
            copia.alforja = (ArrayList) alforja.clone();
            copia.alforja.add(0);
            copia.imprimir();
            llistaAux.add(copia);
            copia = (Alforja) this.clone();
            copia.alforja = (ArrayList) alforja.clone();
            copia.alforja.add(1);
            copia.imprimir();
            llistaAux.add(copia);
        } catch (CloneNotSupportedException ie) {}
        return llistaAux.iterator();
    }

    public int getBound() {
        return 0;
    }

    public void imprimir() {
        for (int i = 0; i < alforja.size(); i++) {
            System.out.print(alforja.get(i));
        }
        System.out.println(" Obj: " + (Integer.MAX_VALUE - getObjective()));
    }

   
}

Application Class

The Aplicacio class demonstrates how to use the Alforja class to solve a specific instance of the Backpack problem.

    public class Aplicacio {
        public static void main(String[] args) {
            Alforja as = new Alforja();
            ArrayList<Integer> a = new ArrayList<>();
            ArrayList<Integer> b = new ArrayList<>();
            Alforja.MAXPES = 50;

            a.add(1);
            a.add(50);
            a.add(10);
            a.add(4);
            a.add(40);
            a.add(20);
            b.add(10);
            b.add(10);
            b.add(30);
            b.add(30);
            b.add(30);
            b.add(20);
            as.setPesos(a);
            as.setValors(b);

            DepthFirstSolver dfs = new DepthFirstSolver();
            as = (Alforja) dfs.solve((Solution) as);
            as.imprimir();
            System.out.println(Integer.MAX_VALUE - dfs.bestObjective);
        }
    }

Maximum Descending Subarray Problem

This code finds the maximum descending subarray within a given array using a divide and conquer approach.

MaximDesc Class

The MaximDesc class represents the problem and solution for finding the maximum descending subarray.

public class MaximDesc implements Problem, Solution {
    private float[] arr;
    private float max;
    private int first, last;

    public MaximDesc(float[] arr, int first, int last) {
        this.arr = arr;
        this.first = first;
        this.last = last;
        this.max = 0;
    }

    public int getFirst() {
        return first;
    }

    public int getLast() {
        return last;
    }

    public float getMax() {
        return max;
    }

    public void setMax(int m) {
        max = m;
    }

    public float[] getArr() {
        return arr;
    }

    public void imprimir() {
        for (int i = first; i <= last; i++)
            System.out.print(arr[i] + " ");
        System.out.println();
    }
}

Maxim Class (Divide and Conquer)

The Maxim class implements the divide and conquer algorithm to solve the MaximDesc problem.

public class Maxim extends DivConqTemplate {
    protected boolean isSimple(Problem p) {
        return (((MaximDesc) p).getLast() - ((MaximDesc) p).getFirst() < 2);
    }

    protected Solution simplySolve(Problem p) {
        int first = ((MaximDesc) p).getFirst();
        int last = ((MaximDesc) p).getLast();
        float[] a = ((MaximDesc) p).getArr();

        ((MaximDesc) p).setMax(Math.max(a[first], a[last]));
        return (Solution) p;
    }

    protected Problem[] decompose(Problem p) {
        int first = ((MaximDesc) p).getFirst();
        int last = ((MaximDesc) p).getLast();
        float[] a = ((MaximDesc) p).getArr();

        int sp = (first + last) / 2;
        Problem[] ps = new MaximDesc[2];

        ps[0] = new MaximDesc(a, first, sp);
        ps[1] = new MaximDesc(a, sp + 1, last);
        return ps;
    }

    protected Solution combine(Problem p, Solution[] ss) {
        float i = Math.max(((MaximDesc) ss[0]).getMax(), ((MaximDesc) ss[1]).getMax());
        ((MaximDesc) p).setMax(i);
        return (Solution) p;
    }
}