どのような種類のアルゴリズムですか？ （ナップザック、ビンパッキング！？）

Question

問題は次のとおりです。

あなたがn日あたりの長さの合計の最大値が最小化されるような日のm個の間で分割する必要がありキロメートルの長さをトリップしています。例えば。 3日間に分割された旅行の長さ[1,5,2,6,8,3,2]は、[1,5,2] [6] [8,3,2]になります。これは、1日の合計の最大値が私達が達成できる最も低いものです。

このような問題の処理方法を説明するアルゴリズムはありますか？私はビンの包装とナップザックの問題に出くわしましたが、どれも私の問題をカバーしていません。私はそれがビンのパッキングの少しの変更かもしれないが、結論に来ないと想像することができます。

Answer 1

この問題は、バイナリ検索

を使用して解決することができる最大の長さは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; 
    } 
} 

時間複雑度は、zはすべての旅行の合計です。

Answer 2

これは、状態がDP[i][j]と定義されている動的プログラミング手法を使用して解決できます。ここで、iは1日の終了インデックスを指し、jはこれまでの日のカウントを保持します。次の状態に移動し、現在の移動に対応する1日の最大合計を取ってから、それを全体の最小値と比較することができます。

C++で再帰的な動的プログラミングソリューションを作成しましたが、状態遷移がどのように機能しているかを理解するのは難しいかもしれません。ソリューションIdeoneへ

#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; 
} 

リンク：https://ideone.com/glHsgF

Answer 3

それはナップザックやビンパッキングでもないのです。それは一般的な名前は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))