AtCoderアルゴリズムと数学演習問題集

Question

AtCoderアルゴリズムと数学演習問題集の009 ”Brute Force 2” を解いています。
009 - Brute Force 2

どこが間違っているのか分かりません。
自分のコードのどこが間違っているか指摘してほしいです。
お願いします。

自分のこれです。

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

template<class T>void ch(T& a, T b) {
	if (a < b)a = b;
}
int main() {
	int i, j;
	long long n, w;
	cin >> n >> w;
	vector<long long>a(n + 1);
	vector<vector<long long>>dp(n + 5, vector<long long>(w + 5, 0));
	for (i = 1; i <= n; i++)cin >> a[i];
	for (i = 1; i <= n; i++) {
		for (j = 0; j <= w; j++) {
			dp[i][j] = dp[i - 1][j];
			if (j - a[i] >= 0) {
				dp[i][j] = a[i];
				ch(dp[i][j], (dp[i][j] += dp[i - 1][j - a[i]]));

			}
		}
	}
	for (i = 1; i <= n; i++) {
		for (j = 0; j <= w; j++) {
			cout << dp[i][j];
		}
		cout << endl;
	}
	if (dp[n][w] == w)cout << "Yes" << endl;
	else cout << "No" << endl;
}

Answer 1

ch(dp[i][j], (dp[i][j] += dp[i - 1][j - a[i]]));
これだと、+= により、関数ch の呼出しの前に dp[i][j] の値が変更されます。
関数ch の中の a は dp[i][j] であり、b は dp[i][j] の値です。
したがって、a の値と b の値は常に等しく、a < b は true になりません。
関数 ch は何もしないことになります。
dp[i][j] + dp[i - 1][j - a[i]] が dp[i][j] より小さいときは
dp[i][j] を変更してはいけないのに、その小さい値に変更されてしまいます。

+= を + に変えてみてください。

追記

			if (j - a[i] >= 0) {
				ch(dp[i][j], a[i] + dp[i - 1][j - a[i]]);
			}

このように変更するとどうなりますか？

どのような入力についてダメな結果になるのですか？

Comments

[TANAKA]

回答ありがとうございます。+に変えてみたのですが元のコードと同じ結果になりました。ありえないことがおきているので、僕のコードがぶち壊れているのだと思います。この回答を参考にしてもう一回組みなおしてみます。

[kazuma-s]

元のコードと同じ結果になったというのは、どのような入力についてどのような結果になったのですか？

[TANAKA]

3 11 4 11
2 5 9 3 1 4 5
Yes No
こうなりました。元コードの＋＝を＋に変えても結果は変わりませんでした。

[kazuma-s]

なぜ、2つの例をひとつにまとめて書くんですか？
しかもこれは AtCoder の問題にある例で出力の yes no は間違っていませんよね。
結果が間違う例を挙げてくださいと言っているのです。
回答に追記したように += を + にするだけではダメで、 a[i] + dp[i-1][j-a[i]] にしないといけません。

[TANAKA]

すいませんこれですね。
5 16
3 4 5 4 1
と入力するとNo（本当はYes）がでます。追記に書いてくださったコードに変えてみてもNoでした。

[kazuma-s]

追記のコードで

5 16
3 4 5 4 1
0 0 0 3 3 3 3 3 3 3 3 3 3 3 3 3 3
0 0 0 3 4 4 4 7 7 7 7 7 7 7 7 7 7
0 0 0 3 4 5 5 7 8 9 9 9 12 12 12 12 12
0 0 0 3 4 5 5 7 8 9 9 11 12 13 13 13 16
0 1 1 3 4 5 6 7 8 9 10 11 12 13 14 14 16
Yes

となりました。

質問のコードの dp[i][j] = a[i]; は削除しましたか？

[TANAKA]

dp[i][j] = a[i]をなくしたらできました。dp[i][j] = a[i]によって一列前の数字をかき消してしまっていたのですね。ありがとうございます。
自分の考えが至らないため、ここまでつきあわせてしまいました。本当にありがとうございます。