什么样的算法? (背包,垃圾桶!?)
What kind of algorithm? (Knapsack, Bin Packing!?)
问题如下:
You have n trip lengths in km which should be divided among m number of days such that the maximum sum of lengths per day is minimized. E.g. The Trip lengths [1,5,2,6,8,3,2] divided among 3 days result in [1,5,2] [6] [8,3,2] because the maximum of the day length sums is the lowest we can achieve.
有没有一种算法描述了这种问题的处理?我遇到了垃圾箱打包和背包问题,但其中 none 个涵盖了我的问题。可以想象可能是对bin packing稍作修改,但不敢下定论。
可以使用动态规划方法来解决,其中状态定义为 DP[i][j]
,其中 i
指一天的结束索引,j
保留一天的计数天到目前为止。您可以移动到下一个状态并获取与当前移动对应的一天的最大总和,然后将其与总体最小值进行比较。
我已经用 C++ 编写了一个递归动态编程解决方案,可能有点难以理解状态转换是如何工作的,您可能需要查看带有记忆的动态编程才能理解它。
#include <iostream>
#define INF 1000000000
using namespace std;
int n, m, dist[100] = {1,5,2,6,8,3,2}, dp[1000][1000];
int solve(int index, int count){
if(index == n){
if(count == m) return 0;
else return INF;
}
if(dp[index][count] != -1) return dp[index][count];
int sum = 0, ans = INF;
for(int i = index;i < n;i++){
sum += dist[i];
int val = max(sum, solve(i+1, count+1));
ans = min(ans, val);
}
return dp[index][count] = ans;
}
int main() {
// your code goes here
n = 7, m = 3;
for(int i = 0;i < 1000;i++) for(int j = 0;j < 1000;j++) dp[i][j] = -1;
cout << solve(0, 0) << endl;
return 0;
}
Link 解决方案 Ideone : https://ideone.com/glHsgF
既不是Knapsack也不是Bin Packing。它的俗称是k分区问题。
如评论中所述,这可以通过使用动态编程来完成。
DP[N,M] - minimum cost of partitioning the array = {a1, ... , aN} into M partitions.
Where cost is defined as the maximum sum of each partition.
DP[1,m] = a1
DP[n,1] = Sum of all elements in the array {a1, ... , an}
DP[n,m] = min over k from 1 to n ( max(DP[n-k,m-1],sum of elements n-k to n))
这个问题可以用二分查找来解决
假设最大长度是 X
,我们可以很容易地检查我们是否可以将行程分成 m 天,每天的最大长度不大于 X
通过以下贪婪:
boolean isValid(int X){
int currentLength = 0;
int numberOfDays = 1;
for(int i = 0; i < n; i++)
if (trip[i] > X)
return false;
if(currentLength + trip[i] <= X){
currentLength += trip[i];
}else{
currentLength = trip[i];
numberOfDays++;
}
}
return numberOfDays <= m;
}
然后,我们可以通过以下二进制搜索轻松找到 X 的最小值:
int start = 0;
int end = sum of all trips;
int result = end;
while(start <=end){
int mid = (start + end)/2;
if(isValid(mid)){
result = mid;
end = mid - 1;
}else{
start = mid + 1;
}
}
时间复杂度为 O(n log z) 其中 z 是所有行程的总和。
问题如下:
You have n trip lengths in km which should be divided among m number of days such that the maximum sum of lengths per day is minimized. E.g. The Trip lengths [1,5,2,6,8,3,2] divided among 3 days result in [1,5,2] [6] [8,3,2] because the maximum of the day length sums is the lowest we can achieve.
有没有一种算法描述了这种问题的处理?我遇到了垃圾箱打包和背包问题,但其中 none 个涵盖了我的问题。可以想象可能是对bin packing稍作修改,但不敢下定论。
可以使用动态规划方法来解决,其中状态定义为 DP[i][j]
,其中 i
指一天的结束索引,j
保留一天的计数天到目前为止。您可以移动到下一个状态并获取与当前移动对应的一天的最大总和,然后将其与总体最小值进行比较。
我已经用 C++ 编写了一个递归动态编程解决方案,可能有点难以理解状态转换是如何工作的,您可能需要查看带有记忆的动态编程才能理解它。
#include <iostream>
#define INF 1000000000
using namespace std;
int n, m, dist[100] = {1,5,2,6,8,3,2}, dp[1000][1000];
int solve(int index, int count){
if(index == n){
if(count == m) return 0;
else return INF;
}
if(dp[index][count] != -1) return dp[index][count];
int sum = 0, ans = INF;
for(int i = index;i < n;i++){
sum += dist[i];
int val = max(sum, solve(i+1, count+1));
ans = min(ans, val);
}
return dp[index][count] = ans;
}
int main() {
// your code goes here
n = 7, m = 3;
for(int i = 0;i < 1000;i++) for(int j = 0;j < 1000;j++) dp[i][j] = -1;
cout << solve(0, 0) << endl;
return 0;
}
Link 解决方案 Ideone : https://ideone.com/glHsgF
既不是Knapsack也不是Bin Packing。它的俗称是k分区问题。
如评论中所述,这可以通过使用动态编程来完成。
DP[N,M] - minimum cost of partitioning the array = {a1, ... , aN} into M partitions.
Where cost is defined as the maximum sum of each partition.
DP[1,m] = a1
DP[n,1] = Sum of all elements in the array {a1, ... , an}
DP[n,m] = min over k from 1 to n ( max(DP[n-k,m-1],sum of elements n-k to n))
这个问题可以用二分查找来解决
假设最大长度是 X
,我们可以很容易地检查我们是否可以将行程分成 m 天,每天的最大长度不大于 X
通过以下贪婪:
boolean isValid(int X){
int currentLength = 0;
int numberOfDays = 1;
for(int i = 0; i < n; i++)
if (trip[i] > X)
return false;
if(currentLength + trip[i] <= X){
currentLength += trip[i];
}else{
currentLength = trip[i];
numberOfDays++;
}
}
return numberOfDays <= m;
}
然后,我们可以通过以下二进制搜索轻松找到 X 的最小值:
int start = 0;
int end = sum of all trips;
int result = end;
while(start <=end){
int mid = (start + end)/2;
if(isValid(mid)){
result = mid;
end = mid - 1;
}else{
start = mid + 1;
}
}
时间复杂度为 O(n log z) 其中 z 是所有行程的总和。