添え字が三つのdpの動かし方

Question

問題

問題

コード

import java.util.Scanner;
public class Anguish {
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int W=scan.nextInt();
        int N=scan.nextInt();
        int K=scan.nextInt();
        int[] A=new int[N];
        int[] B=new int[N];
        for(int i=0;i<N;i++){
            A[i]=scan.nextInt();
            B[i]=scan.nextInt();
        }
        int[][][] dp=new int[N+1][W+1][K+1];

        for(int i=0;i<=W;i++) dp[0][i][0]=0;

        for(int i=0;i<N;i++){
            for(int j=0;j<=W;j++){
                for(int k=0;k<K;k++){
                    if(j>=A[i]){
                        if(dp[i][j-A[i]][k]+B[i]>dp[i][j][k]) dp[i+1][j][k+1]=dp[i][j-A[i]][k]+B[i];
                        else dp[i+1][j][k]=dp[i][j][k];
                    }
                    else dp[i+1][j][k]=dp[i][j][k];
                }
            }
        }
        System.out.println(dp[N][W][K]);
    }
}

#質問内容
ナップサックの問題に追加で制限が付いた問題だったので、添え字を増やして計算していこうと思ってコードを書きました。エラーなどはなく，テストケースは通るのですが提出してみると不正解(WA)と正解(AC)が入り混じった結果となってしまいました。どのような部分がWAを出している可能性があるのかを教えていただければ幸いです。よろしくお願いします。

Answer 1

dp[i][j][k]は、i枚目までの中から、幅がjでかつk枚張り付けた場合の重要度の最大値を意味することになります。そうなると、最後に出力しているdp[N][W][K]は、幅がWでK枚張り付けた場合の重要度の最大値となります。ところが、入力例の説明にもある通り、必ずしもK枚使う必要がなく、また幅も必ずしもWと一致する必要がないと考えられます。
例えばK=10,W=30のような状況で、

• 5枚で幅28、重要度200になる組み合わせがあるが、幅2のスクリーンショットが存在せず幅30にできない
• 6枚で幅30になる組み合わせは存在するものの、その重要度の合計が180となり、最大にならない

という状況が考えられます。これでもこのプログラムは「10枚で幅30の重要度」を表示しますが、この例でそれは実現不可能のため、0を出力する結果となります。当然不正解となります。
このプログラムで正解となるのは、K枚で幅Wを埋めて、かつ条件内での重要度が最大になる、というかなりのレアケースになります。
そのため、動的計画法を使いながら、重要度の最大値を記録しておく必要があると思います。

Comments

[grape_ll]

知識がたりない自分なりには、重要度の最大値を記録していたつもりではあって(K固定にしてしまっているので違うケースはあるだろうなと思いながらですが）どの部分を工夫しなおせばいいのかの推測が出来ていない状態です。特に、かならずしもK枚使わなくてもいいというところの実装の仕方が分からないのですが、よろしければ教えていただけませんでしょうか。

[swordone]

回答の最後に書いてある通り、「全体の重要度の最大値」を記録していくことになります。
ループ外に重要度最大値を記録する変数を置いておき、DP中に出てくる重要度がそれを超えているかによって最大値を更新していきます。

[grape_ll]

なんとなくわかったような気がします．
ありがとうございました．

Answer 2

たとえば、以下のような例でおかしな答えになりませんか？

10
3 2
6 100
3 40
4 20

Comments

[grape_ll]

おかしな答えになっていました。
ｋ枚使い切らない場合のやり方はどのようにするのがいいのでしょうか。