背包0/1变化最大化物体数量，且具有独立的重量限制

Question

我正在尝试使用动态编程来解决背包变体，其中给定一个容器数组，每个容器都有一个重量、一个阻力和一个 ID，我需要找到其中最高的一堆，并具有以下限制:

1. 一个容器不能放置在另一个具有更大 ID 的容器之上。
2. 所有位于另一个容器上方的容器的重量总和不能超过其阻力。 例如： 具有以下容器（Container(id,weight,resistance)） {容器(1,3,3), 容器(2,10,2), 容器(3,10,2), 容器(4,1,2), 容器(5,2,12)} 解为（从上到下）5,4,1。 注意：如果有多个解决方案，程序可以给出其中任何一个，只要它们是正确的。容器按 ID 排序。

我已经通过递归函数和记忆解决了这个问题，但是我无法找到如何正确管理阻力及其随容器重量的变化。

这是我相信我去过的最远的地方：

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

我会这样做：

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) //
        )));
    }
}