正の整数 [a0、a1、a2、...、an] の配列 A と正の数 K があります。次のような配列 A のサブセット U と V のすべての (またはほぼすべての) ペアを見つける必要があります。
- U のすべての要素の合計が K 以下
- V のすべての要素の合計が K 以下
- U + V には、元の配列 A のすべての要素が含まれていない可能性があります
- U のすべての要素は、最初の配列 A の V のすべての要素の前に配置する必要があります。たとえば、U = [a1, a3, a5] を選択すると、a6 からのみ配列 V の構築を開始できるとします。この場合、要素 a0、a2、a4 は使用できません。
O（N ^ 2 * K ^ 2）（NはAの要素の総数）であるDPソリューションを見つけることができました。N と K は小さい (< 100) ですが、それでも遅すぎます。
近似アルゴリズムまたは疑似多項式動的計画法アルゴリズムを探しています。ビン パッキングの問題は私のものと似ていますが、制約にどのように適用できるかわかりません...
お知らせ下さい。
編集: 各数値の上限は 50 です