部分和問題においてメモで計算量をO(NW)にできる理由を教えていただきたいです。
解決したいこと
私はここ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
