5

Given an infinite positive integer array or say a stream of positive integers, find out the first five numbers whose sum is twenty.

問題ステートメントを読むと、最初は問題のように見えますが、整数のストリームで使用0-1 Knapsackできることに混乱しています。0-1 Knapsack algo上記の問題に対して再帰的なプログラムを書いたとしましょう。

int knapsack(int sum, int count, int idx)
{
    if (sum == 0 && count == 0)
        return 1;

    if ((sum == 0 && count != 0) || (sum != 0 && count == 0))
        return 0;

    if (arr[idx] > 20) //element cann't be included.
        return knapsack(sum, count idx + 1);

    return max(knapsack(sum, count, idx +1), knapsack(sum - arr[idx], count -1, idx + 1));
}

max上記の関数が無限配列で呼び出されると、関数 ieの最初の呼び出しはknapsack(sum, count, idx +1)、現在の要素を無視し続けるため、返されません。関数の呼び出しの順序を変更してmaxも、最初の呼び出しが返されない可能性は依然としてあります。knapsackそのようなシナリオでアルゴを適用する方法はありますか?

4

2 に答える 2

5

これは、正の整数のみを使用している場合に機能します。

基本的に、最初の 20 の番号のいずれかに到達できる方法のリストを保持し、新しい番号を処理するたびに、このリストを適切に処理します。

def update(dictlist, num):
    dk = dictlist.keys()
    for i in dk:
        if i+num <=20:
            for j in dictlist[i]:
                listlen = len(dictlist[i][j]) + 1
                if listlen >5:
                    continue
                if i+num not in dictlist or listlen not in dictlist[i+num]:
                    dictlist[i+num][listlen] = dictlist[i][j]+[num]
    if num not in dictlist:
        dictlist[num]= {}
    dictlist[num][1] = [num]
    return dictlist

dictlist = {}
for x in infinite_integer_stream:
    dictlist = update(dictlist,x)
    if 20 in dictlist and 5 in dictlist[20]:
        print dictlist[20][5]
        break

このコードには小さなバグがある可能性があり、今はデバッグする時間がありません。しかし、基本的に dictlist[i][j] は、合計が i になる j 長さのリストを格納します。

于 2012-05-13T05:32:39.880 に答える
0

Delphi コード:

var
  PossibleSums: array[1..4, 0..20] of Integer;
  Value, i, j: Integer;
  s: string;
begin
  s := '';
  for j := 1 to 4 do
    for i := 0 to 20 do
      PossibleSums[j, i] := -1;
  while True do begin
    Value := 1 + Random(20); // stream emulation
    Memo1.Lines.Add(IntToStr(Value));

    if PossibleSums[4, 20 - Value] <> -1 then begin
    //we just have found 5th number to make the full sum
      s := IntToStr(Value);
      i := 20 - Value;
      for j := 4 downto 1 do begin
        //unwind storage chain
        s := IntToStr(PossibleSums[j, i]) + ' ' + s;
        i := i - PossibleSums[j, i];
      end;
      Memo1.Lines.Add(s);
      Break;
    end;

    for j := 3 downto 1 do
      for i := 0 to 20 - Value do
        if (PossibleSums[j, i] <> -1) and (PossibleSums[j + 1, i + Value] = -1) then
          PossibleSums[j + 1, i + Value] := Value;

    if PossibleSums[1, Value] = -1 then
      PossibleSums[1, Value] := Value;
  end;
end;

出力：

4
8
9
2
10
2
17
2
4 2 10 2 2
于 2012-05-13T06:22:51.113 に答える