Rustで動的計画法の実装：Knapsack
はじめに
動的計画法を実装してみて、Rustの勉強をやってみる。問題としてはEducational DP Contestという動的計画法の練習を目的としたコンテストのものを使用。
AからZまで問題が設定されているが、今回はDとEのKnapsack。動的計画法の例題としては有名ですが今まで実装したことは無かった。DとEの違いは制約だけで、Dは価値
完成したコード
解法はいろいろあるが、イメージ的には動的計画法というより、幅優先探索に枝切りをつけたという感じで解いてみた。最終的には以下のようなコードになった。
use proconio::input;
fn main(){
input!(
n: usize, w:i64,
items: [(i64, i64); n],
);
let mut dp: Vec<Vec<(i64,i64)>> = vec![Vec::new(); n];
dp[0].push((0,0)); dp[0].push(items[0]);
for i in 1..n {
let (item_weight, item_value) = items[i];
let mut working = Vec::new();
for (weight, value) in dp[i - 1].clone() {
working.push((weight, value));
if weight + item_weight <= w {
working.push((weight + item_weight, value + item_value));
}
}
working.sort_by(|a,b| {
match a.0.cmp(&b.0) {
std::cmp::Ordering::Equal => a.1.cmp(&b.1).reverse(),
other => other
}
});
let mut max_value = -1;
for element in working.drain(..) {
if element.1 > max_value {
max_value = element.1;
dp[i].push(element);
}
}
}
let (_ans_weight, ans_value) = dp[n - 1].last().unwrap();
println!("{}", ans_value);
}
基本的なアルゴリズム
tupleを使って、価値(w, v)を表す。荷物
for (weight, value) in dp[i - 1].clone() {
working.push((weight, value));
if weight + item_weight <= w {
working.push((weight + item_weight, value + item_value));
}
}
基本的に荷物workingに追加。とりあえず作業用ベクタには、可能性のある組を全部入れてしまう。
dp[i - 1].clone()の部分はclone()なしの状態だとVec<Vec<(i64,i64)>>のindexの外にはmoveできないとコンパイラに怒られたので追加した。clone()の負荷は大きいイメージがあるので、何とかしたい気はするけど、対処法は見つかっていない。
working.sort_by(|a,b| {
match a.0.cmp(&b.0) {
std::cmp::Ordering::Equal => a.1.cmp(&b.1).reverse(),
other => other
}
});
作業用のベクタworkingをソートする。まず重量で昇順にソートし、重量が同じ場合は価値が降順となるようにソートする。
let mut max_value = -1;
for element in working.drain(..) {
if element.1 > max_value {
max_value = element.1;
dp[i].push(element);
}
}
作業用ベクタworkingを、dp[i]に移す時に、価値(w, v)だけを移す。具体的には
workingからdp[i]への「移し替え」について、Rustでは所有権を移すことになるので作業用ベクタから「取り出して（削除して）」渡さないといけない。Rustのpop()が後ろから取り出す仕様だったので、分かりにくいけど逆向きにソートして実装するかなぁと思っていたら、vecから指定された範囲を一括削除し、削除された要素のイテレータを返すdrain()という関数を見つけた。これを、作業用ベクタの全ての範囲を指定して使った。順番が保持されるのかについては明示的な記載が無かったが、説明的には保持されるだろうし、試した範囲では実際に保持されている。
計算量
ナップサック問題は、dp(i)に含まれるtuppleの数 × dp(i)の中の任意のtupleの組みdp(i)に含まれるtuppleの数の最大値は、（重量、価値共に整数値をとるので）ナップサップの上限重量
データ構造について
今回「とりあえず全部挿入」して「ソート」して「条件に合わない要素を削除」している。Listを使ってSorted Listを作って挿入時に条件判断を入れる方が素直な気がするが、リストの場合小さなメモリ断片を大量に確保するのでパフォーマンスが低下する可能性がある。Rustのstd::collections::LinkedListのドキュメントにも以下の記述がある。
NOTE: It is almost always better to use Vec or VecDeque because array-based containers are generally faster, more memory efficient, and make better use of CPU cache.
ちゃんと作ろうとすると、挿入時に削除を行わないといけないので、実装が意外と面倒だったり、その割に計算量のオーダーとしては変わらなかったりするので、とりあえず全部入れてしまってから不要なものを削除するのは悪くない方法だと思う。
荷物の組み合わせを導出する（復元）
どの荷物を詰め込むのがいいか？という所まで導出するには、各tupleにいままでの選択を追加すれば良い。ture, falseの2値の列を保持すればいいのでVec<bool>やビット列でいいのだが、immutableなvectorに1つ要素を足してimmutableなvectorを作る処理が直感的に書けないので文字列にした。
use proconio::input;
fn main(){
input!(
n: usize, w:i64,
items: [(i64, i64); n],
);
+ let mut dp: Vec<Vec<(i64,i64,String)>> = vec![Vec::new(); n];
+ dp[0].push((0,0,String::from("0"))); dp[0].push((items[0].0, items[0].1, String::from("1")));
for i in 1..n {
let (item_weight, item_value) = items[i];
let mut working = Vec::new();
+ for (weight, value, path) in dp[i - 1].clone() {
+ working.push((weight, value, format!("{}0", path)));
if weight + item_weight <= w {
+ working.push((weight + item_weight, value + item_value, format!("{}1", path)));
}
}
working.sort_by(|a,b| {
match a.0.cmp(&b.0) {
std::cmp::Ordering::Equal => a.1.cmp(&b.1).reverse(),
other => other
}
});
let mut max_value = -1;
for element in working.drain(..) {
if element.1 > max_value {
max_value = element.1;
dp[i].push(element);
}
}
}
+ let (_ans_weight, ans_value, ans_path) = dp[n - 1].last().unwrap();
println!("{}", ans_value);
+ for it in ans_path.chars() {
+ if it == '1' { println!("{:?}", items[i]); };
+ i += 1;
+ }
}
出力はこんな感じ
17
(5, 6)
(6, 6)
(3, 5)
計算量の測定
Knapsack問題のgeneratorがあったので、計算量を測定してみる。
問題の種類として、
荷物の数
相関がない下のグラフは数msで終わっているが、相関の強い上のグラフは数百msかかってしまっている。
関連記事
Rustで動的計画法の実装:
🐸Frog | 🌴Vacation | 🎒Knapsack | 🐍LCS | 🚶♂️Longest Path | 🕸️Grid | 💰Coins | 🍣Sushi | 🪨Stones | 📐dequeue | 🍬Candies | 🫥Slimes | 💑Matching | 🌲Indipendent Set | 🌻Flowers | 👣Walk | 🖥️Digit Sum | 🎰Permutation | 🐰Grouping | 🌿Subtree | ⏱️Intervals | 🗼Tower | 🐸Frog3
Discussion