2

私はこの配列を持っています

int arr = new int[] { 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 
978, 978, 978, 978, 978, 978, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 
696, 696, 696, 696, 696, 696, 696, 696, 678, 678, 678, 678, 678, 678, 678, 678, 678, 678, 
446, 446, 446, 446, 446, 446, 446, 446, 446, 446 };

20 elements 978
20 elements 696
10 elements 678
10 elements 446

6000までの合計の最良の組み合わせを見つける必要があります。

Foxの例：

978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

これは最良の組み合わせです。

最適な組み合わせを見つけたら、合計した要素を削除して、もう一度最適な合計を見つける必要があります。

この場合、私の配列は次のようになります。

16 elements 978
17 elements 696
10 elements 678
10 elements 446

次に、次のより良い合計は次のようになります。

 978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

それで：

978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

それで ：

978 + 978 + 978 + 978 + 696 + 696 + 696 = 6000

この瞬間、私の配列は次のとおりです。

4 elements 978
8 elements 696
10 elements 678
10 elements 446

今、私の最高の合計は次のとおりです。

696 + 696 + 696 + 696 + 696 + 696 + 696 + 678 + 446 = 5996

そして私の配列：

4 elements 978
1 elements 696
9 elements 678
9 elements 446

ええと...そして配列が空になるまで合計を行う必要があります。

暗示はありますか？

js、c＃、またはvbである可能性があります。

4

3 に答える 3

0

このトピックにどのように遭遇したかは覚えていませんが、問題を解決するための高速なアルゴリズムを見つけることができたと思います。少なくとも与えられたデータで。私の解決策は、私がより快適に感じるJSにあります。7 ミリ秒未満で解決しますが、高速化が必要な場合は、単純に Haskell または C にトランスコードできると思います。

OK、最初に解決策が表示されないように...

function getSum(arr,sum){
  function getCombinations(arr){
    var len = arr.length,
       subs = Array(Math.pow(2,len)).fill();
    return subs.map((_,i) => { var j = -1,
    	                           k = i,
                                 res = [];
                               while (++j < len ) {
                                 k & 1 && res.push(arr[j]);
                                 k = k >> 1;
                               }
                               return res;
                             }).slice(1);
  }
  function getPossibles(a,t){
    var fo = a[0],
    maxTry = Math.min(Math.floor(t/fo.n),fo.c);

    return a.length > 1 ? Array(maxTry).fill()
                                       .map((_,i) => ({n:fo.n, c:maxTry-i}))
                                       .reduce((p,c) => (p.push(...getPossibles(a.slice(1),t-c.n*c.c).map(e => a.length > 2 ? [c,...e]
                                                                                                                            : [c,e])),p),[])
                        : [{n:fo.n, c: maxTry}];
  }
  var  hash = arr.reduce((p,c) => (p[c] ? p[c]++ : p[c] = 1,p),{}),
   condense = Object.keys(hash)
                    .reverse()
                    .map(k => ({n: k, c:hash[k]}));
     combos = getCombinations(condense);
  possibles = combos.reduce((p,c) => (c.length > 1 ? p.push(...getPossibles(c,sum))
                                                   : p.push(getPossibles(c,sum)),p),[]);
  return possibles.filter(p => p.reduce((s,o) => s += o.n*o.c,0) === sum)
                  .map(e => e.reduce((p,c) => p.concat(Array(c.c).fill(c.n)),[]));
}

var arr = [978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 978, 696, 696, 696, 696, 696, 696, 696, 696 ,696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 696, 678, 678, 678, 678, 678, 678, 678, 678, 678, 678, 446, 446, 446, 446, 446, 446, 446, 446, 446, 446],
 result = [],
     ps = 0,
     pe = 0;
ps = performance.now();
result = getSum(arr,6000);
pe = performance.now();
console.log(result);
console.log("Done in:", pe-ps);

コードをできるだけ明示的にしようとしました。ここでは順を追って説明しようと思います。

この問題を解決する関数がgetSum()あり、その中に と の 2 つのユーティリティ関数がgetCombinations()ありgetPossibles()ます。

値の配列 ( arr) とターゲット ( sum) を受け取ったら、まず下にハッシュ テーブルを作成hashします。

{ '446': 10, '678': 10, '696': 20, '978': 20 }

明らかに、どの番号が何回存在するかを伝えることで、配列のマップを提供します。

次に、配列をより単純な形式のオブジェクトに再マッピングし、次のように保存しcondenseます

[ { n: '978', c: 20 },
  { n: '696', c: 20 },
  { n: '678', c: 10 },
  { n: '446', c: 10 } ]

この時点で、後ですべての可能性を解決できるように、これらのオブジェクトの組み合わせを取得する必要があります。このタスクでは、getCombinations()ユーティリティ関数を利用しています。次のようになります。

[ [ { n: '978', c: 20 } ],
  [ { n: '696', c: 20 } ],
  [ { n: '978', c: 20 }, { n: '696', c: 20 } ],
  [ { n: '678', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '678', c: 10 } ],
  [ { n: '696', c: 20 }, { n: '678', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '696', c: 20 }, { n: '678', c: 10 } ],
  [ { n: '446', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '446', c: 10 } ],
  [ { n: '696', c: 20 }, { n: '446', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '696', c: 20 }, { n: '446', c: 10 } ],
  [ { n: '678', c: 10 }, { n: '446', c: 10 } ],
  [ { n: '978', c: 20 }, { n: '678', c: 10 }, { n: '446', c: 10 } ],
  [ { n: '696', c: 20 }, { n: '678', c: 10 }, { n: '446', c: 10 } ],
  [ { n: '978', c: 20 },
    { n: '696', c: 20 },
    { n: '678', c: 10 },
    { n: '446', c: 10 } ] ]

これで、何を試すかがわかりました。しかし、私たちは賢く試みなければなりません。目標の合計が 6000 であることはわかっているので、過剰な計算を許可するべきではありません。ここがトリッキーな部分です。count (プロパティ) の値が合計で 6000 以下getPossibles()のオブジェクトのみを返すユーティリティ関数があります。c

OkgetPossibles()は、オブジェクトの配列 (圧縮されたデータ) を受け取り、合計が 6000 未満のセットの可能な組み合わせを提供し[ { n: '978', c: 20 }, { n: '696', c: 20 }, { n: '678', c: 10 } ]ます。

[ [ { n: '978', c: 5 }, { n: '696', c: 1 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 4 }, { n: '696', c: 3 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 4 }, { n: '696', c: 2 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 4 }, { n: '696', c: 1 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 4 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 3 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 2 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 3 }, { n: '696', c: 1 }, { n: '678', c: 3 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 5 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 4 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 3 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 2 }, { n: '678', c: 3 } ],
  [ { n: '978', c: 2 }, { n: '696', c: 1 }, { n: '678', c: 4 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 7 }, { n: '678', c: 0 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 6 }, { n: '678', c: 1 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 5 }, { n: '678', c: 2 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 4 }, { n: '678', c: 3 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 3 }, { n: '678', c: 4 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 2 }, { n: '678', c: 5 } ],
  [ { n: '978', c: 1 }, { n: '696', c: 1 }, { n: '678', c: 6 } ] ]

ええと...このデータを手元に置くことができれば、持っているものを減らすのは簡単なことです。つまり、最後の 1 行だけです。

possibles = combos.reduce((p,c) => (c.length > 1 ? p.push(...getPossibles(c,sum))
                                                 : p.push(getPossibles(c,sum)),p),[]);
                  .filter(p => p.reduce((s,o) => s += o.n*o.c,0) === sum)
                  .map(e => e.reduce((p,c) => p.concat(Array(c.c).fill(c.n)),[]));

JS で 7 ミリ秒未満でソリューションを取得する方法です。

于 2016-10-15T19:26:31.640 に答える
0

.. C# での私のコードは次のとおりです。

Dictionary ex = new Dictionary<Integer,Short>();

ex.Add(978, 20); // 20 elements 978
ex.Add(696, 20); // 20 elements 696
ex.Add(678, 10); // 10 elements 678
ex.Add(446, 10); // 10 elements 446

すべての要素の配列の代わりに使用する方が時間効率が高く、毎回合計を計算する代わりに、合計を事前に計算しました。

class Ex
{
    Dictionary<Integer,Short> ex;
    long sum;

    public Ex ()
    {
        ex = new Dictionary<Integer,Short>();
        sum = 0;
    }

    public void add (int number, short frequency)
    {
        ex.Add(number, frequency);
        sum += (number * frequency);
    }

    public void remove (int number)
    {
        sum -= (number * ex.Get(number));
        ex.Remove(number);
    }

    public void increment (int number, short frequency)
    {
        ex.Set(number, ex.Get(number)+frequency);
        sum += (number * frequency);
    }

    public void subtract (int number, short frequency)
    {
        ex.Set(number, ex.Get(number)-frequency);
        sum -= (number * frequency);
    }

    public long getSum ()
    {
        return sum;
    }
}

お役に立てれば ..

于 2013-03-18T18:28:21.347 に答える