Rustコトハジメ

プログラミング言語Rustに関する情報をお届けします。

個数制限つきナップザック問題の考え方

個数制限付きナップザック問題にかなり苦戦したので、考え方を書き残しておきます。

個数制限つきナップザック問題とは

個数制限つきナップザック問題とは以下のような問題です。

https://onlinejudge.u-aizu.ac.jp/problems/DPL_1_G

f:id:akiradeveloper529:20190307135206j:plain

愚直に考えてTLE

www.rustforbeginners.com

コイン問題の時と同様に、2次元のDPテーブルを作り、d[i][j] = max(dp[i-1][j], dp[i-1][j-kw]+kv)を愚直に実装しましたが、O(NWM)で10乗オーダなのでTLEしました。当たり前ですね。

真の解法

というわけでより効率的な解法が必要になりますが、残念ながら全く思いつきませんでした。ぐぐったり他人の解法を見ても、一体何をしてるのかなかなかわからなかったですが、最終的にはわかったので、それをわかりやすく書きます。

01ナップザックに帰着

まず第一段階として、(v,w,m)は(v,w)をmを並べることで01ナップザックに帰着させることが出来ます。とるかとらないか選択していけば、0個からm個までとるケースを網羅出来ることは自明ですね。というかO(NWM)の解法というのは、実質的にはこういうことをしているのに等しいです。

m個をlogm個に圧縮する

例えばですが、15(24-1)という数字を1,2,4,8に分割するとします。すると0から15の間の数字はこれらの数字の組み合わせで全部作れることは自明ですよね。では、中途半端な14の場合はどうでしょう?これは最後の数字を7に1つ減らせば、出来ることは自明ですね。(最後の要素を使う場合で調整を行っているからです) 同様に数字一般について、このように分割することで0からその数字までをすべて作れることがわかります。

問題に戻ると、mをa,b,c,...に分割して、(av,aw),(bv,bw),(cv,cw),...の01ナップザックにしても、結局0個からmまでを作れるのですから、上で述べた(v,w)をmを並べる01ナップザックと同じ解を導けることがわかります。

それを実装してAC出来ました。

fn solve() {
    input! {
        N: usize, W: usize,
        X: [(usize,usize,usize); N],
    };

    let mut vw = vec![];
    for i in 0..N {
        let (v,w,mut m) = X[i];
        let mut j=0;
        while m > 0 {
            let k = min(m, 1<<j);
            m -= k;
            vw.push((k*v,k*w));
            j+=1;
        }
    }

    let mut dp = vec![0; W+1];
    for (v,w) in vw {
        for i in (0..W+1).rev() {
            if i>=w {
                dp[i] = max(dp[i], dp[i-w]+v);
            }
        }
    }

    let mut r=0;
    for j in 0..W+1 {
        r=max(r,dp[j]);
    }
    println!("{}",r);
}