Rustコトハジメ

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

巨大ナップザック問題の考え方 (半分全列挙)

AOLのライブラリコースのうちDPLにはさまざまな種類のナップザック問題が詰め込まれており、どれもエッセンスとしては重複がないので良問と思いました。そのうち、巨大ナップザック問題の考え方を紹介します。初見では全く太刀打ち出来なかったです。

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

f:id:akiradeveloper529:20190307134446j:plain

f:id:akiradeveloper529:20190307134532j:plain

この問題は形は単なるナップザック問題ですが、

  • wやvが異常にでかい。つまり、wやvでのDPは出来ない
  • Nは小さい

という特徴があります。Nは小さいですが、総当たりで調べると240=1012で、明らかに無理です。

考え方

ポイントは、

  • N=20ならば総当たり出来る
  • M=220=106とすると、総当たりした計算結果の組み合わせを調べることは、MlogMで出来る

です。考え方としてはマージソートに近いと思いました。

解法

ナップザックなのでDPのカテゴリに入っていますが、DPではないです。

  • 商品を2つにわけて、それぞれで(sum_w, sum_v)のリストを作ります // (1)
  • (片方だけで良いのでこちらをリスト2とします) sum_wについて昇順、同一のsum_wについてはsum_vについて降順でソートします // (2)
  • i<jとして、sum_vについてi番目がj番目より高い場合、j番目のものは明らかに劣っているからとる理由がない。後の探索から除外するため、以前の最大値でsum_vを上書きします // (3)
  • リスト1を総なめして、「自分に足りない重量のうちで最高価格のもの」をリスト2から探します。リスト2をソートしておいたために二分探索が使えることが自慢です // (4)
/// [(v,w)] -> [(sum_w,sum_v)]
fn mk_h(xs: &[(u64,u64)]) -> Vec<(u64,u64)> {
    let mut res = vec![];
    let n=xs.len();
    for i in 0..(1<<n) {
        let mut sum_w = 0;
        let mut sum_v = 0;
        for j in 0..n {
            if (i & (1<<j)) > 0 {
                sum_w += xs[j].1;
                sum_v += xs[j].0;
            }
        }
        res.push((sum_w,sum_v));
    }
    res.sort_by_key(|&(w,v)| (w,Rev(v)));
    let mut v = 0;
    for i in 0..res.len() {
        v = max(res[i].1, v);
        res[i].1 = v; // (3)
    }

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

    let h1 = mk_h(&X[0..N/2]);
    let h2 = mk_h(&X[N/2..]);

    let mut ans = 0;
    for (sum_w1,sum_v1) in h1 {
        if W >= sum_w1 {
            let i = h2.lower_bound(&(W-sum_w1+1, 0)); // (4)
            ans = max(ans, sum_v1+h2[i-1].1);
        }
    }

    println!("{}", ans);
}

考察

リストがソートされているという条件を保つことで、ナイーブに考えるとNかかる探索を二分探索によりlogNに減らすというテクニックは時々見る気がします。今後問題を見る時には注意したいです。

例えば蟻本で紹介されているLISのアルゴリズムは、dpテーブルを

dp[i] = i+1の長さのLISを作るときの最小の末尾

と定義することによって、二分探索によって各長さi+1を作る時の最小の末尾を更新し続けることが出来ます。