背包问题的这种变体需要最小重量。目标是最小化成本,同时至少实现最小重量。
例如,我们有 6 件物品,重量为
{1, 1, 1, 5, 13, 3}
,成本为 {1, 1, 1, 5, 10, 12}
。
假设最小重量为 15。
最佳解决方案是物品
{1, 2, 5}
,总重量为 15,成本为 12。
我应该如何尽可能有效地实现这个算法?贪婪的选择不起作用,那么我是否应该修改原始的动态规划解决方案来适应这个问题?如果是的话,怎么办?
如果重要的话,我打算用 Java 来写这个。
设
minCost[i]
表示容量为i
的背包所能容纳的最小值,costs[i]
表示第i件物品的成本,weights[i]
表示第i件物品的重量。然后,对于每个 i,minVal[i]
是从 1 到项目数的所有 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);
这可以通过将大于或等于最小权重的所有权重组合成一个状态来优化。这减少了时间和内存复杂性,使其仅取决于问题给出的最小权重。
final int[] weights = { 1, 1, 1, 5, 13, 3 }, costs = { 1, 1, 1, 5, 10, 12 };
final int minWeight = 15;
final int[] minCost = new int[minWeight + 1];
Arrays.fill(minCost, Integer.MAX_VALUE);
minCost[0] = 0;
for (int i = 0; i < weights.length; i++) {
for (int w = minWeight; w >= weights[i]; w--) {
final int prev = Math.max(w - weights[i], 0);
if (minCost[prev] != Integer.MAX_VALUE)
minCost[w] = Math.min(minCost[w], minCost[prev] + costs[i]);
}
}
System.out.println(minCost[minWeight]);
让我们定义函数 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)
我们实际上可以通过稍微修改@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