3

重みの固定リストがあります：

int[] weights = new int[] { 10, 15, 20 };

およびターゲット：

int target = 28;

私は、 （繰り返しが許可されている）targetからの要素の合計として表現するアルゴリズムを探しています。これは、一致または超過し、可能な限り最も近い一致が達成され、その中で使用される重みの数が最小限に抑えられます。weightstargettarget

したがって、上記の入力では、10 20または15 15を返す必要があります。これ30は、可能な限り近いためであり、作成のオプションの30うち、これら2つは。よりも優れてい10 10 10ます。

のを使用するtargetと39、出力は、、、または20 20ではなく、になります。15 15 1010 10 10 10

のを使用するtargetと14、出力はになります15。

通常のforeachループ以外に、ここで良いアプローチはありますか？配列で使用可能な最大値を取得して、ターゲットが負であるかどうかを確認することを考えていました。負でない場合は、次の値に進みましょう。

これは宿題ではありません:)

4

2 に答える 2

3

これはナップサック問題として知られています。唯一の違いは、最も近い下位の一致ではなく、最も近い一致を探していることです。また、幸いなことに、どの重みにも異なる値はありません。難しいのは、最も近いものの1つを単純に使用して、残りの値を使用して再帰することができないことです（小さい値を組み合わせると、より適切に一致する場合があります）。weights

あなたの例では、weightsすべての間に5つの「ユニット」があります。これが常に当てはまる場合、問題の解決は非常に簡単になります。

于 2012-07-10T08:30:38.280 に答える
2

ここにいるみんなのおかげで解決策を見つけることができ、実際に何が必要かがもう少し明確になりました。これは私が書いた中で最も美しいコードではありませんが、とにかくこれはMVP開発です！

private static List<int> WeightsJuggle(List<int> packages, IOrderedEnumerable<int> weights, int weight)
{
    if (weight == 0)
        return packages;

    foreach (int i in weights.Where(i => i >= weight))
    {
        packages.Add(i);
        return packages;
    }

    packages.Add(weights.Max());
    return WeightsJuggle(packages, weights, weight - weights.Max());
}

私はそれをこのように呼びます

IOrderedEnumerable<int> weights = new int[] { 10, 15, 20 }.OrderBy(x => x);
int weight = 65;
List<int> packages = new List<int>();

重量65でテスト

ここに画像の説明を入力してください

重量123でテスト

ここに画像の説明を入力してください

于 2012-07-10T09:16:07.013 に答える