代码之家 › 专栏 › 技术社区 › Igl3

什么样的算法?(背包、垃圾箱包装!?)

bin-packing knapsack-problem algorithm

5

Igl3 · 技术社区 · 9 年前

问题如下:

您有n个以公里为单位的行程长度,应在m天数之间进行划分,以使每天的最大长度总和最小化。E、 g.行程长度[1,5,2,6,8,3,2]除以3天得出[1,5,1][6][8,3,1],因为天数总和的最大值是我们能达到的最低值。

是否有一种算法可以描述此类问题的处理?我遇到过垃圾箱包装和背包问题,但没有一个能解决我的问题。我可以想象这可能是对垃圾箱包装的一点修改,但并没有得出结论。

3 回复 | 直到 9 年前

1

4

A. Sarid arch 9 年前

这个问题可以使用二进制搜索解决

假设最大长度为 X ,我们可以很容易地检查是否可以将行程划分为m天,每天的最大长度不超过 十、 以下是贪婪的:

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) 具有是所有行程的总和。

2

3

uSeemSurprised 9 年前

它可以使用动态规划方法进行求解,其中状态定义为 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;
}

链接到解决方案Ideone: https://ideone.com/glHsgF

3

A. Sarid arch 9 年前

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))