3

この問題はプログラミング競争によるものであり、許容できる時間内に解決することはできません。

整数の配列が与えられaます。与えられた整数を超えない正確な要素（必ずしも連続ではない）nの最大の合計を見つけます。skm (s < m)

制約：

 0 < k <= n < 100
 m < 3000
 0 < a[i] < 100

情報：与えられた入力に対してソリューションが存在することが保証されています。

さて、私の最善の策はDPアプローチだと思いますが、正しい式を思い付くことができませんでした。

4

4 に答える 4

2

私は2つのことを試みます。どちらも次のアイデアに基づいています。

正確にk合計する要素があるかどうかを判断する問題を解決できれば、で答えを二分探索できます。p[1, m]

1.最適化されたブルートフォース

配列を並べ替えて、現在の合計がを超えたら検索を短くしますp。ソートされた配列は悪い解決策を早期に排除するのに役立つはずなので、一般的にはほとんどバックトラックする必要がないという考え方です。

正直なところ、これで十分な速さになるとは思えません。

2.ランダム化されたアルゴリズム

usedサイズの配列を保持しますk。ランダムに要素を割り当てます。それらの合計はそうではありませんがp、要素をランダムに別の要素に置き換え、一定時間内にそれらの合計を更新するようにしてください。

これを最大e回数続けます（最良の結果を得るための値を使用した実験では、複雑さが最終的には高くなる可能性があるため、おそらくかなり高くなる可能性があります）。この間O(e log m)に合計を得ることができなかった場合は、そうではないと想定します。p可能。

または、二分探索を忘れてください。eランダム化されたアルゴリズムを直接実行し、実行中または割り当てられた実行時間が終了するまで、検出された最大の有効な合計を返します。

DPが合計で使用される要素の数を効率的に追跡する方法がわかりません。ランダム化アルゴリズムは実装が簡単なので、一見の価値があると思います。

于 2013-02-27T20:01:28.910 に答える
2

受け入れられた方法は両方とも劣っています。また、これはDPで解決できる問題タイプではありません。

以下は、例を示した正しい方法です。

a = {2、3、5、9、11、14、17、23}（したがって、n = 8）、k = 3、およびs=30を想像してください。

配列をソートします。

1からnまでの3つのポインター、P1、P2、およびP3を配列に定義します。P1 <P2 <P3

P3をa_max（ここでは23）、P1を1、P2を2に設定します。合計sを計算します（ここでは23 + 2 + 3 = 28）。s> Sの場合は、P3を1つ減らし、解決策が見つかるまで再試行します。P3 <3の場合、解決策はありません。最初のソリューションをこれまでで最もよく知られているソリューション（BKSSF）として保存します。

次に、s> SになるまでP2を増やします。より良い解決策が見つかった場合は、BKSSFを更新します。P2を1つ減らします。

次に、s>SになるまでP1を増やします。より良い解決策が見つかった場合は更新します。

ここでP2に戻り、1つ減らします。

次に、s>SなどになるまでP1を増やします。

これは再帰的アルゴリズムであり、増加または減少するたびに、対応する1つ以上の減少、増加が見られます。

このアルゴリズムは、上記の試みよりもはるかに高速です。

于 2013-03-01T20:59:52.777 に答える
0

l<=kおよびr<=sの場合：

V [l] [r] = trueの場合、合計がrになるl個の要素を正確に選択できます。

V[0][0] = true
for i in 1..n:
  V'[][] - initialize with false
  for l in 0..k-1:
    for r in 0..s:    
      if V[l][r] and s + a[i] <= s:
        V'[l + 1][r + a[i]] = true
  V |= V'

これにより、O（k * n * s）で達成可能なすべての合計が得られます。

于 2013-03-01T22:00:49.193 に答える
0

タイラー・ダーデンは正しい考えを持っていたと思います。ただし、すべての要素を合計する必要はなく、基本的には貪欲に行うことができるため、ループを大幅に削減できます。C ++の場合：

#include <iostream>
#include <algorithm>
using namespace std;

#define FI(n) for(int i=0;i<(n);i++)

int m, n, k;
int a[] = { 12, 43, 1, 4, 3, 5, 13, 34, 24, 22, 31 },
    e[20];

inline int max(int i) { return n-k+i+1; }

void print(int e[], int ii, int sum)
{   cout << sum << '\t';
    FI(ii+1) cout << e[i]<<','; cout<<'\n';
}

bool desc(int a, int b) { return a>b; }

int solve()
{   sort(a, a+n, desc);
    cout <<"a="; FI(n) cout << a[i]<<','; cout<<"\nsum\tindexes\n";
    int i,sum;
    i = e[0] = sum = 0;
    print (e,i,a[0]);
    while(1)
    {   while (e[i]<max(i) && sum+a[e[i]]>=m) e[i]++;
        if (e[i]==max(i))
        {   if (!i) return -1;  // FAIL
            cout<<"*"; print (e,i,sum);
            sum -= a[e[--i]++];
        } else // sum+a[e[i]]<m
        {   sum += a[e[i]];
            print (e,i,sum);
            if (i+1==k) return sum;
            e[i+1] = e[i]+1;
            i++;
        }
    }
}

int main()
{   n = sizeof(a)/sizeof(int);
    k = 3;
    m = 39;
    cout << "n,k,m="<<n<<' '<<k<<' '<<m<<'\n';
    cout << solve();
}

m = 36の場合、出力が得られます

n,k,m=11 3 36
a=43,34,31,24,22,13,12,5,4,3,1,
sum indexes
43  0,
34  1,
*34 1,10,
31  2,
35  2,8,
*35 2,8,11,
34  2,9,
35  2,9,10,
35

m = 37の場合、

n,k,m=11 3 37
a=43,34,31,24,22,13,12,5,4,3,1,
sum indexes
43  0,
34  1,
*34 1,10,
31  2,
36  2,7,
*36 2,7,11,
35  2,8,
36  2,8,10,
36

（最後の1回の試行：m = 39の場合、正しい答えも得られます、38）出力：最後の数値は合計であり、その上の行にはインデックスがあります。アスタリスクの付いた行はバックトラックの前にあるため、行の最後のインデックスが高すぎます。ランタイムはO（k * n）である必要があります。

わかりにくいコードでごめんなさい。リクエストに応じてクリーンアップして説明することはできますが、現在別のプロジェクトが予定されています;）。

于 2013-05-08T09:30:33.413 に答える