最小重量背包

Question

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

如果有关系的话，我打算用Java写这个。

Answer 1

让mincost[i]表示具有i容量的背包所能容纳的最小值，coste[i]表示第ith项的成本，weights[i]表示第ith项的重量。然后，对于每个i，minval[i]是所有j的minval[i-weights[j]]+costes[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);

演示