Knapsack 0/1 variation maximize the number of objects with independent weight restrictions

Question

I'm trying to use dynamic programming to solve a knapsack variation, where you are given an array of containers, each of them having a weight, a resistance and an id, I need to find the tallest pile of them with the following restrictions:

1. A container can't be placed above another with a bigger id.
2. The total sum of the weight of all the containers above another one can't surpass its resistance. For example: Having the following containers (Container(id,weight,resistance)) {Container(1,3,3), Container(2,10,2), Container(3,10,2), Container(4,1,2), Container(5,2,12)} The solution would be (from top to bottom) 5,4,1. Note: If there's more than one solution, the program can give any of them as long as they are correct. The containers come ordered by id.

I've already solved the problem with a recursive function and memoization, however I'm incapable of finding how to properly manage resistances and their variations with the weight of the containers.

This is the furthest I've believe I've been:

public static List<Container> findBestPile(List<Container> containers){
    int n = containers.size();
    int[] dp = new int[n];
    int[] previous = new int[n];
    int[] resistance = new int[n];
        
    Arrays.fill(dp, 1);
    Arrays.fill(previous, -1);
        
    for(int i = 0; i < n; i++) resistance[i] = containers.get(i).resistance;

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            // Verify if object i can be after object j
            if (containers.get(i).weight <= resistance[j] && dp[j] + 1 > dp[i]) {
                dp[i] = dp[j] + 1;
                previous[i] = j;
                resistance[i] = Math.min(resistance[j] - containers.get(i).weight, containers.get(i).resistance);
            }
        }
    }
    // Find biggest index in dp
    int maxIndex = 0;
    for (int i = 1; i < n; i++) {
        if (dp[i] > dp[maxIndex]) {
            maxIndex = i;
        }
    }

    // Reconstruct the biggest pile from the "previous" array
    List<Container> bestPile = new ArrayList<>();
    for (int i = maxIndex; i != -1; i = previous[i]) {
        bestPile.add(containers.get(i));
    }

    return bestPile;
}

Answer 1

I'd do it like this:

public class Piles {
    record Box(int id, int weight, int strength) {}
    record Pile(Box first, Pile next, int weight) {}

    static Pile findLargestPile(Box...boxes) {
        /*
         * We use induction along boxes, starting from the back,
         * while maintaining a list of all piles that:
         * 1. only contain boxes we have already seen
         * 2. contain them in the proper order
         * 3. do not collapse under their own weight
         * 4. have minimum weight for their size
         */
        var pile = new Pile[boxes.length + 1];
        pile[0] = new Pile(null, null, 0); // the empty pile has height 0
        var bestHeight = 0;
        
        for (int i = boxes.length - 1; i >= 0; i--) {
            var newBox = boxes[i];
            for (int h = bestHeight; h >= 0; h--) {
                if (newBox.strength >= pile[h].weight) {
                    var newPile = new Pile(newBox, pile[h], newBox.weight + pile[h].weight);
                    if (h == bestHeight) {
                        pile[h + 1] = newPile;
                        bestHeight = h + 1;
                    } else if (newPile.weight < pile[h + 1].weight) {
                        pile[h + 1] = newPile;
                    }
                }
            }
        }
        return pile[bestHeight];
    }
    
    static StringBuilder format(Pile p) {
        if (p.first == null) {
            return new StringBuilder();
        }
        return format(p.next).append(p.first).append(" totalWeight=").append(p.weight).append("\n");
    }
    
    public static void main(String[] args) {
        System.out.print(format(findLargestPile(
                new Box(1, 3, 3), //
                new Box(2, 10, 2), //
                new Box(3, 10, 2), //
                new Box(4, 1, 2), //
                new Box(5, 2, 12) //
        )));
    }
}