背包问题中的最小重量

Question

这个背包问题的变种需要达到一个最小重量。目标是在至少达到最小重量的情况下，最小化成本。

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

最优解是选取物品{1, 2, 5}，总重量为15，成本为12。

我应该如何以最高效的方式实现这个算法？贪心选择不能奏效，那么我应该修改原始的动态规划解决方案以适应这个问题吗？如果是这样，应该怎么做？

如果有影响的话，我计划用Java编写代码。

- Nimbus

---

为什么最优解不是物品 {1, 2, 5}？ - Unmitigated

是的，非常感谢您指出这一点。我已经进行了更改。 - Nimbus

Answer 1

让 minCost[i] 表示容量为 i 的背包可容纳的最小值，costs[i] 表示第 i 个物品的成本，而 weights[i] 表示第 i 个物品的重量。对于每个 i，minVal[i] 是所有 j（从 1 到物品数）中 minVal[i - weights[j]] + costs[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);

演示

- Unmitigated

---

非常感谢！您能否提供此算法的时间复杂度和简要说明？ - Nimbus

@Nimbus 这是 O(nm) 的时间复杂度，其中 n 是物品数量，m 是最大重量。 - Unmitigated

Answer 2

我们可以通过稍微修改@Unmitigated的答案，实际上实现O(n * targetMinWeight)而不是O(n * maximum weight)。

class Solution:


    def knapsack(self, n, costs, weights, target):
        MAX = float('inf')
        dp = [[0 for _ in range(n + 1)] for _ in range(target + 1)]
        for t in range(target + 1):
            dp[t][0] = MAX
        for i in range(n + 1):
            dp[0][i] = MAX

        for t in range(1, target + 1):
            for i in range(1, n + 1):
                if t > weights[i - 1]:  # i - 1 because of the offset
                    dp[t][i] = min(dp[t][i - 1], dp[t - weights[i - 1]][i - 1] + costs[i - 1])
                else:
                    dp[t][i] = min(dp[t][i - 1], costs[i - 1])

        return min(dp[target])

sol = Solution()
print(sol.knapsack(6, [1, 1, 1, 5, 10, 12], [1, 1, 1, 5, 13, 3], 15)) # returns 12

- ryanym

Answer 3

让我们定义函数f(i,j)，它给出了从前i+1个物品（0,1…i）中选择物品且重量之和恰好为j的最小成本，那么至少得到重量（minW=15）的最小成本将如下计算：

min(f(i,j)) where  i=0,1...n-1, j=minW,minW+1,.... maxW 
- n is the number of items 
- minW=15 in your case
- maxW is the maximum possible sum of all the given weights

你可以参考这段C++代码（非常类似于Java）：

    const int maxW = 100;//the maximum weight, a problem constraint
    const int maxN = 100;//the maximum number of items, a problem constraint

    int n = 6; //input
    int w[maxN] = { 1, 1, 1, 5, 13, 3 };//the weights(should be read as an input)
    int c[maxN] = { 1, 1, 1, 5, 10, 12 };//the costs(should be read as an input)
    
    int f[maxN][maxW];
    for (int i = 0; i < maxN; i++)
        for (int j = 0; j < maxW; j++)
            f[i][j] = 1000000;//some big value

    int minW = 15;//the minimum weight(should be read as an input)
    
    int result = 1000000;
    
    f[0][w[0]] = c[0];//initialization
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < maxW; j++) {
            
            f[i][j] = f[i - 1][j];//don't pick the i-th item

            if (j - w[i] >= 0) {//pick the i-th item if possible
                if (f[i][j] > f[i - 1][j - w[i]] + c[i])
                    f[i][j] = f[i - 1][j - w[i]] + c[i];
            }

            if (j >= minW and f[i][j] < result) {
                result = f[i][j];//store the minimum cost when the weight is >= minW
            }
        }
    }
    cout << result << endl;//print the result(12 in this case)

- VFX