4

私は、重み付きの間隔のセットを取り、重みを最大化する2人の「ワーカー」間でそれらを最適に分散するコードを作成しようとしています。入力の例は次のようになります。

9
1 2 1
1 3 3
2 4 1
3 5 1
4 6 2
5 7 1
6 8 2
7 9 1
8 10 2

「9」は間隔の量であり、列は次のように定義されます。

s f v

s=start time
f=finish time
v=weight

これまで、二分探索を使用して、直前の間隔である「p」値を決定し、それを配列に格納してきました。そこから、入力変数を1つずつ調べて、最大の重みと、現在の間隔をいずれかのワーカーの「キュー」に含めるかどうかを決定します。

これまでの私のコードは次のとおりです。

#include <stdio.h>
#include <stdlib.h>

#define TABSIZE (100)

int n,s[TABSIZE],f[TABSIZE],v[TABSIZE],p[TABSIZE],M[TABSIZE],M2[TABSIZE];


int binSearchLast(int *a,int n,int key)
{
// Input: int array a[] with n elements in ascending order.
//        int key to find.
// Output: Returns subscript of the last a element <= key.
//         Returns -1 if key<a[0].
// Processing: Binary search.

int low,high,mid;
low=0;
high=n-1;

// subscripts between low and high are in search range.
// size of range halves in each iteration.
// When low>high, low==high+1 and a[high]<=key and a[low]>key.
while (low<=high){
    mid=(low+high)/2;
    if (a[mid]<=key)
        low=mid+1;
    else
        high=mid-1;
}

return high;
}

main()
{
int i,j,sum=0,sum2=0;

scanf("%d",&n);
f[0]=(-999999); // For binarySearchLast
for (i=1;i<=n;i++)
    scanf("%d %d %d",&s[i],&f[i],&v[i]);
for (i=2;i<=n && f[i-1]<=f[i];i++);
    if (i<=n){
        printf("Intervals not ordered by finish time %d\n",__LINE__);
        exit(0);
    }

for (i=1;i<=n;i++)
    p[i]=binSearchLast(f,n+1,s[i]);

M[0]=0;
M2[0]=0;

//checks to see if the resulting weight is bigger in a certain queue
for (i=1;i<=n;i++){
    if(v[i]+M[p[i]]>M[i-1] && !(v[i]+M2[p[i]]>M2[i-1]))
        M[i]=v[i]+M[p[i]];
    else if(v[i]+M2[p[i]]>M2[i-1] && !(v[i]+M[p[i]]>M[i-1]))
        M2[i]=v[i]+M2[p[i]];
    else
        M[i]=M[i-1];
}


printf("\n\nroom 1:\n\n");
for (i=n;i>0; ){
    if (v[i]+M[p[i]]>=M[i-1]){
        printf("%d %d %d\n",s[i],f[i],v[i]);
        sum+=v[i];
        i=p[i];
    }
    else
        i--;
}
printf("\n\nroom 2:\n\n");
for (i=n;i>0; ){
    if (v[i]+M2[p[i]]>=M2[i-1]){
        printf("%d %d %d\n",s[i],f[i],v[i]);
        sum2+=v[i];
        i=p[i];
    }
    else
        i--;
}

printf("sum 1 is %d\n",sum);
printf("sum 2 is %d\n",sum);
}

これは部屋1でも機能するようですが、部屋2は何らかの理由でまったく同じキューで出てきます。これは私の現在の出力です：

room 1:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

room 2:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

「正しい」出力が次のようになる場合：

room 1:

8 10 2
6 8 2
4 6 2
2 4 1
1 2 1

room 2:

7 9 1
5 7 1
3 5 1
1 3 3

任意の洞察をいただければ幸いです。

編集**それを見ると、結果を印刷するときにM[]とM2[]に含まれる間隔を決定する方法に実際に関係しているのではないかと思います。2つの部屋の出力が同じであるのは偶然のようです。私はまだそれを修正するために何をすべきかを理解していませんが、私はまだアドバイスを探しています。

4

1 に答える 1

1

まず、要件について...

「重みを最大化する2人のワーカー間でタスクを最適に分散する」と言う場合、（a）開始と終了の間隔に基づいて重複するタスクがないように、（b）最も多くのワーカーにタスクを割り当てたいと思います。可能な作業は、実際には労働者に割り当てられています。タスクが重複しすぎると、重複しているため、2人のワーカーにすべてのタスクを割り当てることができない場合があります。（テストデータを使用して、すべてのタスクを割り当てることができます。）

もしそうなら、これはナップサック問題のバリエーションですが、2つのナップサックがあります。この問題は「NP困難」であることが知られており、実用的な目的では、コーディングしたよりも複雑なソリューションが必要になることを意味します。再帰プログラミングを使用したものであることは間違いありません。ただし、十分ではあるが一般的には最適ではない答えを生成する、より単純なアルゴリズムがあります。

第二に、あなたの解決策について...

コードの中央セクションには注意が必要です。あなたが持っている：

M[0]=0;
M2[0]=0;

//checks to see if the resulting weight is bigger in a certain queue
for (i=1;i<=n;i++){
    if(v[i]+M[p[i]]>M[i-1] && !(v[i]+M2[p[i]]>M2[i-1]))
        M[i]=v[i]+M[p[i]];
    else if(v[i]+M2[p[i]]>M2[i-1] && !(v[i]+M[p[i]]>M[i-1]))
        M2[i]=v[i]+M2[p[i]];
    else
        M[i]=M[i-1];
}

私は自由に変数名を拡張しました：

// Cumulative weights of tasks assigned to workers 1 and 2.
// E.g., load1[5] is total weight of tasks, selected from
// tasks 1..5, assigned to worker 1.     
load1[0] = 0;
load2[0] = 0;

// checks to see if the resulting weight is bigger in a certain queue
for (i = 1; i <= count; i++){
    if  (weight[i] + load1[prior[i]] > load1[i-1]
    && !(weight[i] + load2[prior[i]] > load2[i-1]))
        load1[i] = weight[i] + load1[prior[i]];
    else
    if  (weight[i] + load2[prior[i]] > load2[i-1]
    && !(weight[i] + load1[prior[i]] > load1[i-1]))
        load2[i] = weight[i] + load2[prior[i]];
    else
        load1[i] = load1[i-1];
}

IFステートメントは、次の4つの可能性のうちの2つにweight[i]のみload1対応しload2ます。あなたのコードは、との両方で良い場合、またはどちらでも良い場合には対応していません。また、それぞれについて、コードは両方に割り当てるか、両方に割り当てないため、ループの最後で、配列値の半分が未定義になります。load2load1weight[i]load1load2iload1[i]load2[i]

このため、常にload1ゼロで埋めるデフォルトのELSEに移動します。ループの終わりでは、load1ゼロでいっぱいで、load2未定義*です（を除くload2[0]）。

印刷ループの後半では、すべてゼロになると、最初の印刷ループがpriorテーブルを逆方向​​にホップして、表示される結果を印刷します。初期化されていないload2配列もたまたまゼロである可能性があるため、2番目の印刷ループも同じことを行います。

何をすべきか？保証された最適なアルゴリズムが必要な場合は、ナップサック問題を調べることをお勧めします。「十分な」アルゴリズムで十分な場合は、いくつかの単純なアルゴリズムを試して（たとえば、各タスクを容量のある最初のワーカーに渡す）、さまざまなテストデータセットでどのように実行されるかを確認できます。

（*技術的には、プログラムでload2暗黙的に宣言されているためstatic、Cコンパイラーによってゼロに初期化されますが、これに依存しないでください。）

于 2012-07-19T05:10:38.053 に答える