背包最小重量

Question

背包问题的这种变体需要最小重量。目标是最大限度地降低成本，同时至少实现最小的重量。

例如，我们有 6 件物品，有重量{1, 1, 1, 5, 13, 3}和成本{1, 1, 1, 5, 10, 12}。假设最小重量为 15。

最佳解决方案是{1, 2, 5}总重量为 15 且成本为 12 的物品。

我应该如何尽可能有效地实现这个算法？贪婪的选择不起作用，那么我是否应该修改原始的动态规划解决方案来适应这个问题？如果是这样，怎么办？

如果重要的话，我打算用 Java 来写这个。

Answer 1

设minCost[i]表示一个有容量的背包所能容纳的最小值i，costs[i]表示第 i 件物品的成本，weights[i]表示第 i 件物品的重量。然后，对于每个 i，是从 1 到项目数的minVal[i]最小值。minVal[i - weights[j]] + costs[j]j

minCost那么答案就是数组中从最小权重到最大权重范围内的最小值。

final int[] weights = { 1, 1, 1, 5, 13, 3 }, costs = { 1, 1, 1, 5, 10, 12 };
final int minWeight = 15;
int maxWeight = 0;
for (final int weight : weights) {
    maxWeight += weight;
}
final int[] minCost = new int[maxWeight + 1];
for (int i = 1; i <= maxWeight; i++) {
    minCost[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < weights.length; i++) {
    for (int j = maxWeight; j >= weights[i]; j--) {
        if (minCost[j - weights[i]] != Integer.MAX_VALUE) {
            minCost[j] = Math.min(minCost[j], minCost[j - weights[i]] + costs[i]);
        }
    }
}
int answer = Integer.MAX_VALUE;
for (int i = minWeight; i <= maxWeight; i++) {
    answer = Math.min(answer, minCost[i]);
}
System.out.println(answer);

Demo

这可以通过将大于或等于最小权重的所有权重组合成单个状态来优化。这减少了时间和内存复杂性，使其仅取决于问题给出的最小权重。

final int[] weights = { 1, 1, 1, 5, 13, 3 }, costs = { 1, 1, 1, 5, 10, 12 };
final int minWeight = 15;
int maxWeight = 0;
for (final int weight : weights) {
    maxWeight += weight;
}
final int[] minCost = new int[maxWeight + 1];
for (int i = 1; i <= maxWeight; i++) {
    minCost[i] = Integer.MAX_VALUE;
}
for (int i = 0; i < weights.length; i++) {
    for (int j = maxWeight; j >= weights[i]; j--) {
        if (minCost[j - weights[i]] != Integer.MAX_VALUE) {
            minCost[j] = Math.min(minCost[j], minCost[j - weights[i]] + costs[i]);
        }
    }
}
int answer = Integer.MAX_VALUE;
for (int i = minWeight; i <= maxWeight; i++) {
    answer = Math.min(answer, minCost[i]);
}
System.out.println(answer);