java - 最小重量的背包

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，minVal[i]是 minVal[i - weights[j]] + costs[j] 的最小值所有 j从 1 到项目数。
那么，答案是 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