主页 / coding / 问题 / 79256066
Accepted
Nombre de Usuario Genérico
Asked: 2024-12-06 03:53:10 +0800 CST

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

  • 772

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

  1. 一个容器不能放置在另一个具有更大 ID 的容器上方。
  2. 所有容器上方的重量总和不能超过其阻力。例如：具有以下容器 (Container(id,weight,resistance)) {Container(1,3,3), Container(2,10,2), Container(3,10,2), Container(4,1,2), Container(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;
}
algorithm

1 个回答

  1. Best Answer

    我会这样做：

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

相关问题