Before reading the article, you must know about bit operation.
If you don't know about it, I recommend to read this article
What is bit DP?
bit DP is a technique that can often be used in situations where you want to find the optimal permutation among possible permutations of n elements.
bit DP is a below dynamic programming framework.
- dp[S] := When optimizing the order within a subset
Sof the entire set{0, 1, ,..., n - 1), minimum cost inS.
In the bit DP framework, the following recurrence formula often holds:
- dp[S] = min(S, dp[S-i] + cost(S-i, i));
The following is a brief explanation of the meaning of this formula.
We want to compute the cost dp[S] of optimizing the order in it for S. We divide the case by what was the last element of the order.
If the last of S was i, then the optimal solution for the subset of S excluding the last i of S is dp[S- {i}]. If the increasing cost by adding i to S-{i} was cost(S-i, i), minimum cost is dp[S-i] + cost(S-i, i).
Then give i a try of all of them in the range of S and adopt the one that has the lowest cost.
Try to Solve a practical problem!
https://onlinejudge.u-aizu.ac.jp/problems/DPL_2_A
It is the problem of optimizing the order over n cities, so we can use bit DP.
However a little bit of ingenuity is required.
Looking at the bit DP's recurrence formula,
- dp[S] = min(S, dp[S-{i}] + cost(S-{i}, i));
S - idepends on which city was last, for example cost(u, i) if the last city was u, so we can't decide dp[S]. To solve it, we fix the dp table as below: - dp[S][v] := the minimum cost in S for a subset S of the whole set {0, 1, ,..., n - 1} when the ordering is optimized with the constraint that the last is v.
DP reduction formulas can also be realized with a small modification:
- dp[S][v] = min(S, dp[S-v][u] + dist[u][v]);
Based on this, the implementation would be as follows
macro_rules! input {
(source = $s:expr, $($r:tt)*) => {
let mut iter = $s.split_whitespace();
let mut next = || { iter.next().unwrap() };
input_inner!{next, $($r)*}
};
($($r:tt)*) => {
let stdin = std::io::stdin();
let mut bytes = std::io::Read::bytes(std::io::BufReader::new(stdin.lock()));
let mut next = move || -> String{
bytes
.by_ref()
.map(|r|r.unwrap() as char)
.skip_while(|c|c.is_whitespace())
.take_while(|c|!c.is_whitespace())
.collect()
};
input_inner!{next, $($r)*}
};
}
macro_rules! input_inner {
($next:expr) => {};
($next:expr, ) => {};
($next:expr, $var:ident : $t:tt $($r:tt)*) => {
let $var = read_value!($next, $t);
input_inner!{$next $($r)*}
};
}
macro_rules! read_value {
($next:expr, ( $($t:tt),* )) => {
( $(read_value!($next, $t)),* )
};
($next:expr, [ $t:tt ; $len:expr ]) => {
(0..$len).map(|_| read_value!($next, $t)).collect::<Vec<_>>()
};
($next:expr, chars) => {
read_value!($next, String).chars().collect::<Vec<char>>()
};
($next:expr, usize1) => {
read_value!($next, usize) - 1
};
($next:expr, $t:ty) => {
$next().parse::<$t>().expect("Parse error")
};
}
const INF: i64 = 1 << 60;
// main implementation
pub fn main() {
input!(
n: usize,
m: usize,
data: [(usize, usize, i64); m]
);
let dist = {
let mut dist = vec![vec![INF; n]; n];
for (s, t, d) in data {
dist[s][t] = d;
}
dist
};
let mut dp = vec![vec![-1; n + 1]; 1 << n];
let res = rec(n, 0, 0, &mut dp, &dist);
if res != INF {
println!("{}", res);
} else {
println!("-1");
}
}
fn rec(n: usize, s: usize, now_v: usize, dp: &mut Vec<Vec<i64>>, dist: &Vec<Vec<i64>>) -> i64 {
let mut res = INF;
// Valid only if all have been explored and the current position is at the start.
if s == (1 << n) - 1 {
if now_v == 0 {
dp[s][now_v] = 0;
} else {
dp[s][now_v] = INF;
}
return dp[s][now_v];
}
for v in 0..n {
if (s >> v) & 1 == 0 && dist[v][now_v] != INF {
res = res.min(rec(n, s | 1 << v, v, dp, dist) + dist[v][now_v]);
}
}
dp[s][now_v] = res;
dp[s][now_v]
}
Top comments (0)