LoginSignup
crignactor
@crignactor (クリグナ)

Are you sure you want to delete the question?

Leaving a resolved question undeleted may help others!

部分和問題においてメモで計算量をO(NW)にできる理由を教えていただきたいです。

Q&AClosed
C++アルゴリズム

解決したいこと

私はここ1週間で競プロに興味を持ちC++とアルゴリズムの勉強を始めた理系大学生で、プログラミング歴も1ヶ月くらいです。部分和問題について、再帰を使うアルゴリズムで、メモを使用するかしないかで計算量が変わる理由を伺いたいです。
メモを使うと計算量がO(2^N)からO(NW)になるそうなのですが、この場合フィボナッチ数列のように同じ計算が出てくるわけではないと思うので、メモが計算量を減らす理由が私には分からないです。

私が間違っているとは思うので、
おそらく同じ計算が出てくるということなのだと考えているのですが、その場合、処理過程のどこで同じ計算が出てくるのですか？

メモを使用しないコード

#include <bits/stdc++.h>
using namespace std;

bool func(int i, int w, const vector<int> &a) {
    vector<int>totals(i,-1);

    sort(a.begin(),a.end());
// �١���������
    if (i == 0) {
        if (w == 0) return true;
        else return false;
    }
    if (totals.at(i-1==-1)){
   for (int x=0;x<i;x++){
    totals.at(i-1)+=a.at(x);
}
}
    if (totals.at(i-1)<w) return false;


    if (func(i - 1, w, a)) return true;


    if (func(i - 1, w - a[i - 1], a)) return true;

    return false;
}

int main() {
    int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];
    if (func(N, W, a)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

メモを使用するソースコード

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

// func(i, w, a) の答えをメモ化する配列
vector<vector<int>> memo;

// 0：false、1: true
int func(int i, int w, const vector<int> &a) {
    // ベースケース
    if (i == 0) {
        if (w == 0) return true;
        else return false;
    }

    // メモをチェック (すでに計算済みならば答えをリターンする)
    if (memo[i][w] != -1) return memo[i][w];

    // a[i - 1] を選ばない場合
    if (func(i - 1, w, a)) return memo[i][w] = 1;

    // a[i - 1] を選ぶ場合
    if (func(i - 1, w - a[i - 1], a)) return memo[i][w] = 1;

    // どちらも false の場合は false
    return memo[i][w] = 0;
}

int main() {
    // 入力
    int N, W;
    cin >> N >> W;
    vector<int> a(N);
    for (int i = 0; i < N; ++i) cin >> a[i];

    // 再帰的に解く
    memo.assign(N+1, vector<int>(W+1, -1));
    if (func(N, W, a)) cout << "Yes" << endl;
    else cout << "No" << endl;
}

例）

def greet
  puts Hello World
end

自分の考え

メモの添字はiとwですので、iとwが共に重複するものについては、計算の手間が省けるということは分かります。しかし、このコードでfunc()はi,wの値の組が同じ引数をとらないように思います(最悪時間計算量を考えるときには配列aの要素が特殊で計算量が少なくなる場合を除くから)。
なぜなら、wにはWそのものか、Wからaの要素いくつかを引いたものが入りますが、そのどれも等しくならないからです。iについても同様です。そして、そのそれぞれを1回ずつ計算するだけで、1+2+2^2+…+2^N=O(2^N )の計算量になると考えるからです。

参考資料

『問題解決力を鍛える！アルゴリズムとデータ構造』大槻兼資・秋山拓哉著
https://github.com/drken1215/book_algorithm_solution

0

3Answer

actorbug
@actorbug

色々伝えたいことはあるのですが、まとまらないので、ただ並べるだけにします。

メモを使うと計算量がO(2^N)からO(NW)になるそうなのですが、この場合フィボナッチ数列のように同じ計算が出てくるわけではないと思うので、メモが計算量を減らす理由が私には分からないです。

O(2^N)からO(NW)になっても、計算量が減るとは限りません。

例えば、(1,10,100,1000,10000)の部分和として2000を作れるか、という問題を考えます。
そうすると、2^N=2^5=32、NW=5*2000=10000となり、明らかに2^Nの方が小さくなります。

動的計画法が効果的なのは、NとWが小さい場合だけです。
Wが大きい場合は、メモを使わない方がよい場合も出てきます。

なお、ここで提示されている「メモを使用するソースコード」にはバグがあります。

2 4
1 5

こちらの入力の場合、計算途中でwがマイナスとなり、memo[i][w]にてマイナスのインデックスにアクセスすることになります。
マイナスのインデックスへのアクセスは「未定義動作」となり、何が起こるか分かりません。
GCCの場合は、ヘッダのインクルード前に「#define _GLIBCXX_DEBUG」を入れれば、明示的にエラーにしてくれます。

メモを使用する場合、wがマイナスだったらfalseを返すコードを追加する必要があります。
このコードを追加することで、2^N回の計算を行う前に、途中で打ち切られるケースが出てくるため、計算量が減ります。

ただ、こちらの効果はメモ化とは無関係なので、メモ化しない方に適用しても計算量は減ります。

計算過程で一切同じ計算が出てこないような部分和問題を作ることは可能です。

例えば、(1,2,4,8,16)の部分和を考えると、和が1～31となる組み合わせはそれぞれ1通りしかないため(2進数で考えれば分かると思います)、メモを使っても計算量は変わりません。

しかし、上で説明した「wがマイナスならfalseを返す」により減る分により、O(NW)には収まります。

メモの存在意義は、「確実に計算回数がNW回に収まる」ところにあります。
メモ用に確保したNW個のメモリを埋めれば、計算が終了することが保証できます。
そのため、O(NW)である、と言い切ることができます。

メモが無い場合、計算途中で同じ結果が発生すると、その組み合わせの数により倍々で計算量が増えていくのを止める手段がありません。
そのため、上限まで考えると、O(2^N)であるとまでしか言えないことになります。

2
PondVillege
@PondVillege

はじめに

標準入力から与えられるN,W,a[N]の意味を察するに，ナップサック問題と同様，N個の品物があり，i番目の品物の重さがa[i]に格納され，ナップサックの重さはWにしたい．できる場合はYes，そうでない場合はNoということでしょうか．明言されていないのでこれを前提に話を進めます．

O(2^N)について

$N$個の物の中から，選ぶor選ばないの$2$パターンを全て列挙すると$2^N$になります1．この組み合わせ1つ1に対して判定をするのは$O(1)$なので列挙に時間がかかり$O(2^N)$です．

O(NW)について

まず，

wにはWそのものか、Wからaの要素いくつかを引いたものが入りますが、そのどれも等しくならないからです

に関しては要議論です．i番目以降からN-1番目までの間の部分和のパターン数が$2^{N-1-i}$個あり，この列挙した品物の重さの和は等しくなることもあるのではないでしょうか？

次の入力ケース

5 11
5 4 3 2 1

の場合ではコードのように配列の最後1から4まで調べる(i=1時点)と，重さの和は次のようにいろんなケースが列挙されます．

  • $10$: 4 + 3 + 2 + 1
  • $9$: 4 + 3 + 2
  • $8$: 4 + 3 + 1
  • $7$: 4 + 3，4 + 2 + 1
  • $6$: 4 + 2，3 + 2 + 1
  • $5$: 4 + 1，3 + 2
  • $4$: 4，3 + 1
  • $3$: 4，2 + 1
  • etc...

このケースにおいて重さ$3\leq w\leq 7$では配列の先頭5に到達するまでに重複するケースが頻発しています．品物列挙のパターン数が指数関数的に多いことから発生する状態だと考えた方が良い気がします．

競プロというか整数論をやっていると，ある整数になる積の組み合わせを考えるより，和の組み合わせの方がパターンが多すぎて解析が難しい，という感覚になるのですがどうでしょう．

余談

@drken さんの著書で困っている件であること，引用したコードのリンクや引用していることの明言など，もう少し情報が欲しいところでした．剽窃とされる可能性もあるので注意しましょう．

  1. $N$個の物に対して状態が$M$個あると全部で$M^N$パターンです． ↩

1

Comments

  1. @crignactor

    Questioner
    ありがとうございました。
    nが十分大きくなると、0〜Wの個数より2^nがはるかに大きくなるので当然重なってくるということですね。nの小さい場合から間違った類推をしてしまっていました。NW≦2^Nの場合を考えないと違いが一般的な入力に対しては生じないのは当然ですよね。
    先程、ナップサック問題を学んで自分でも気づいたのですが、改めて自分がどうして間違った推論をしてしまったのか考えられ理解することができました。

    引用元を書かなかった件については、軽率だったと反省してます。実は自分で調べたとき同じようなコードがいくつか出てきてたので、大丈夫かなと思ってしまいました。すごい人には分かるし、本当に非常識でした。次から気をつけます。

    前回の質問もですが色々勉強になります。ありがとうございます。
crignactor
@crignactor

ありがとうございます。
計算量の上限を保証するというのは、昨日ナップサック問題をやって学んだことではあるのですが、本にも書いていなかったたため、少しフワッとした理解をしていました。おっしゃるようなメモリを確保するという観点はなかったので、より深く理解できたと思います。
インデックスが負の数の場合、0になるようなのですけど、アルゴ式で試してみたら、答えを導けない入力もあったので、おっしゃるような条件を足したらうまく行っていました。何でなのかと思っていたんですが、普通はインデックスが正であるという条件をつけないとならないということなのですね。
ありがとうございました。

0

Your answer might help someone💌

LoginSign Up

Popular Questions