具有两个权重的背包算法
knapsack algorithm with two weights
我有以下问题:
Solve the knapsack 0-1 problem(not fractional) Assuming that every
object have weight w1
or w2
(there only two weights). Capacity=W, the algorithm
must run on O(nlogn).
我试过求解,贪心算法不行,动态规划算法是O(n*W)。
谁能给我点提示。
谢谢。
因为有两个权重,您可以:
首先使用尽可能多的元素 w1,或者可以放入 W。然后使用尽可能多的 w2。
当你得到这样的背包时,在每次迭代中从中弹出一个 w1 元素,并放入尽可能多的 w2 或你有。只要背包中有 w1 个元素,就可以这样做。
所有迭代中背包的最大重量将是您的答案,算法将在 O(n)
中 运行
您可以将元素分成两部分,一部分的权重为 w1
,另一部分的权重为 w2
。
现在您可以根据成本对以上两个列表进行排序。
A1 : sorted by cost in descending order, elements that have weight as w1
A2 : sorted by cost in descending order, elements that have weight as w2
现在您可以创建两个数组的前缀和,我们称它们为 P1, P2
。
示例:
Array : 11, 8, 5, 3, 1
Prefix sum : 11, 19, 24, 27, 28
获得前缀总和后,您可以遍历 P1
数组并尝试将元素包含到第 i 个索引。
一旦我们包含最多 i
个元素,我们还剩下 W - (w1*i)
个权重,然后我们可以尝试在 P2
数组中对这个权重进行二进制搜索。
伪代码:
A : input array
create A1 : cost of elements having w1 weight
create A2 : cost of elements having w2 weight
sort(A1, descending)
sort(A2, descending)
for(i=0;i <= A1.size();i++){
P1[i] = P1[i-1] + A1[i];
P2[i] = P2[i-1] + A2[i];
}
int ans = 0;
for(i=1;i<=A1.size();i++){
if(i * w1 <= W){
int wLeft = W - i * w1;
int ans = binarySearch(wLeft, P2) + p1[i];
}
}
ans => contains the answer
//-----------Binary search function
int binarySearch(int weight, P2[]){
int start = 0, end = P2.size(), ans = 0;
int mid = (start+end)/2;
while(start <= end){
if(mid * w2 <= weight){
start = mid + 1;
ans = max(ans, p2[mid]);
}else{
end = mid - 1;
}
}
return ans
}
整体复杂度为O(n * log n)
。
按照@j_random_hacker的建议,我们可以迭代第二个前缀数组,因为我们只能通过添加元素来改进解决方案,它会通过删除二进制搜索来简化代码。
我有以下问题:
Solve the knapsack 0-1 problem(not fractional) Assuming that every object have weight
w1
orw2
(there only two weights). Capacity=W, the algorithm must run on O(nlogn).
我试过求解,贪心算法不行,动态规划算法是O(n*W)。
谁能给我点提示。 谢谢。
因为有两个权重,您可以:
首先使用尽可能多的元素 w1,或者可以放入 W。然后使用尽可能多的 w2。
当你得到这样的背包时,在每次迭代中从中弹出一个 w1 元素,并放入尽可能多的 w2 或你有。只要背包中有 w1 个元素,就可以这样做。
所有迭代中背包的最大重量将是您的答案,算法将在 O(n)
中 运行您可以将元素分成两部分,一部分的权重为 w1
,另一部分的权重为 w2
。
现在您可以根据成本对以上两个列表进行排序。
A1 : sorted by cost in descending order, elements that have weight as w1
A2 : sorted by cost in descending order, elements that have weight as w2
现在您可以创建两个数组的前缀和,我们称它们为 P1, P2
。
示例:
Array : 11, 8, 5, 3, 1
Prefix sum : 11, 19, 24, 27, 28
获得前缀总和后,您可以遍历 P1
数组并尝试将元素包含到第 i 个索引。
一旦我们包含最多 i
个元素,我们还剩下 W - (w1*i)
个权重,然后我们可以尝试在 P2
数组中对这个权重进行二进制搜索。
伪代码:
A : input array
create A1 : cost of elements having w1 weight
create A2 : cost of elements having w2 weight
sort(A1, descending)
sort(A2, descending)
for(i=0;i <= A1.size();i++){
P1[i] = P1[i-1] + A1[i];
P2[i] = P2[i-1] + A2[i];
}
int ans = 0;
for(i=1;i<=A1.size();i++){
if(i * w1 <= W){
int wLeft = W - i * w1;
int ans = binarySearch(wLeft, P2) + p1[i];
}
}
ans => contains the answer
//-----------Binary search function
int binarySearch(int weight, P2[]){
int start = 0, end = P2.size(), ans = 0;
int mid = (start+end)/2;
while(start <= end){
if(mid * w2 <= weight){
start = mid + 1;
ans = max(ans, p2[mid]);
}else{
end = mid - 1;
}
}
return ans
}
整体复杂度为O(n * log n)
。
按照@j_random_hacker的建议,我们可以迭代第二个前缀数组,因为我们只能通过添加元素来改进解决方案,它会通过删除二进制搜索来简化代码。