2

私は制約プログラミングが初めてで、数値で構成される 2 次元配列から、元の 2D 配列をできるだけ多くカバーして、可能な限り最小限のサブ配列 (2D) を取得する必要があるという問題を解決しようとしています。可能な限り、次の規則に従います。

  • すべてのサブ配列は、元の長方形の部分でなければなりません
  • 各サブ配列の数値の合計は、特定の数値を超えてはなりません
  • すべてのサブ配列には、少なくとも 2 つの数値が含まれている必要があります

たとえば、次のマトリックスの場合:

3 5 1 4
5 1 2 8
0 8 1 3
8 3 2 1

最大合計が 10 の場合、ソリューションは次のようになります。

 3 -not picked 
{ 5 1 4 }
{ 5 1 }
{ 2 8 }
{ 0 8 }
{ 1 3 
  2 1 }
 8 -not picked

現在、or-tools ( MakeNonOverlappingBoxesConstraint() ) に相当するdiffn()を使用して、元の配列を覆う四角形を作成しています。

私の問題は、diffn() によって作成された四角形を取得し、それぞれの位置とサイズに基づいて元のマトリックスを分割する方法です。そのため、Sum制約を適用できます。

diffn() を使用せずに同じ制約を達成する別の方法がある場合は、それを試してみますが、他の方法は考えられません。

ありがとうございました！

4

1 に答える 1