1

より多くの反応を引き出すために、MathExchange に相互投稿しま​​した。

================================================== ==============================

元の質問を StackOverflow で書いていたときに、以前に質問されたことに気付きました。

部分和問題と呼ばれるものがあることが判明したので、ウィキペディアに行ってこの部分を見つけました。

The algorithm for the approximate subset sum problem is as follows:
 initialize a list S to contain one element 0.
 for each i from 1 to N do
   let T be a list consisting of xi + y, for all y in S
   let U be the union of T and S
   sort U
   make S empty 
   let y be the smallest element of U 
   add y to S 
   for each element z of U in increasing order do
      //trim the list by eliminating numbers close to one another
      //and throw out elements greater than s
     if y + cs/N < z ≤ s, set y = z and add z to S 
 if S contains a number between (1 − c)s and s, output yes, otherwise no

しかし、ウィキペディアに書かれた疑似コードを理解するのに問題があります。

たとえば、目的は S に一致する最も近い数のセットを見つけることだと思いました。

しかし、ここで S はリストです。この要素が 0 の S リストは何ですか?

そして、一体何 if y + cs/N < z ≤ sですか？これをコードに書き出すにはどうすればよいですか？

誰かがこれをphpコードに翻訳するのを手伝ってくれることを望んでいました.

少なくとも私はそのことに精通しています。完全な翻訳である必要はありません。

答えがこのおおよそのアルゴリズムを理解して、自分でphpコードで書くのに十分である限り、それで十分です。

4

1 に答える 1

3

math.stackexchange.com に投稿したサブ質問に 1 つずつ回答するには:

S大きいと 小さいはどう違いsますか？bigSは、最初はリスト[0]であり、コードの実行中に変更されるリスト変数です。少しsは一定のままの数です。具体的にsは、この質問の番号です。

整数のセットと整数sが与えられた場合、空でない部分集合の合計はsになりますか?

しかし、とにかく、何ですか？ S大まかに言えば、Sこれまで見てきた要素を使用して作成できるすべての「有用な」合計のセットを表します (私が間違っていなければ)。

「要素0のリスト」とは、ゼロである単一の数値を含むリストを意味しますか? はい、そういう意味です。

とはy + cs/N < z ≤ sどういう意味ですか? y + c*s/N < zとという意味ですz ≤ s。そのため、または(または両方)のif場合はいつでも失敗します。y + c*s/N ≥ z z > s

そして、あなたが尋ねなかったが、出てくる可能性が高いと思われるいくつかの質問:

とはN? N与えられたセット内の要素の数です。

とはxi? xi与えられたセットのi番目の要素です。

于 2013-08-22T18:16:40.190 に答える