読者です 読者をやめる 読者になる 読者になる

ABC 60-D Simple Knapsack

こんにちは。今日はABC60でしたね。

D問題はナップザックだと思って以下のようなコードを書いたのですが、WAだったので自分のコードがWAするテストケースを考えました。

public static long solve(int index, long weight, long value) {
    String s = index + "," + weight;
    if (w < weight) {
        return Integer.MIN_VALUE;
    } else if (memo.containsKey(s)) {
        return memo.get(s);
    } else if (index == n) {
        return value;
    } 
    
    long temp = Math.max(
            solve(index + 1, weight, value),
            solve(index + 1, weight + weights[index], value + values[index])
    );
    memo.put(s, temp);
    
    return temp;
}

こんなテストケースを考えてみます。

4 3
1 100
1 2
2 3
9 10

このテストケースではこのプログラムは5を返します。間違ってます。

問題点

どこが問題なのかを探るために、この関数が呼ぶすべての引数を図にしてみます。 f:id:ilovehugeworld:20170430002410p:plain

問題が起きる箇所まで戻り値とmemoを埋めてみます。 f:id:ilovehugeworld:20170430003347p:plain

問題点が見つかりました。solve(2, 1, 100)でカバンのなかにすでに100の価値があるのに、memoから5を返しているのです。これは間違ってます。つまり、このコードの問題点は現在のカバンの中にある価値を考えずに、すでに探索したことがある場合その最大値を返しているところです。

改善案

valueを関数に渡すのではなく、戻ってきた値に足しましょう。

public static long solve2(int index, long weight) {
    String s = index + "," + weight;
    if (w < weight) {
        return Integer.MIN_VALUE;
    } else if (index == n) {
        return 0;
    } else if (memo.containsKey(s)) {
        return memo.get(s);
    }
    long temp = Math.max(
            solve2(index + 1, weight), 
            values[index] + solve2(index + 1, weight + weights[index])
    );
    
    memo.put(s, temp);
    return temp;
}

これで、ACがもらえます。教訓はDPを書くときは戻り値にコストを加えるということです。 問題点は@eiyaさんに指摘してもらいました。ありがとうございました!