competitive/combinatorial_optimization/
knapsack_problem.rs

1use std::{
2    cmp::Ordering,
3    collections::VecDeque,
4    mem::swap,
5    ops::{Add, Neg},
6};
7
8#[derive(Debug, Clone)]
9pub struct KnapsackPloblemSmallWeight {
10    pub dp: Vec<i64>,
11}
12
13impl KnapsackPloblemSmallWeight {
14    pub fn new(max_weight: usize) -> Self {
15        let mut dp = vec![i64::MIN; max_weight + 1];
16        dp[0] = 0;
17        Self { dp }
18    }
19    pub fn max_weight(&self) -> usize {
20        self.dp.len() - 1
21    }
22    pub fn insert(&mut self, value: i64, weight: usize) {
23        for i in weight..self.dp.len() {
24            if self.dp[i - weight] != i64::MIN {
25                self.dp[i] = self.dp[i].max(self.dp[i - weight] + value);
26            }
27        }
28    }
29    pub fn extend<I>(&mut self, iter: I)
30    where
31        I: IntoIterator<Item = (i64, usize)>,
32    {
33        for (value, weight) in iter.into_iter() {
34            self.insert(value, weight);
35        }
36    }
37    pub fn insert01(&mut self, value: i64, weight: usize) {
38        for i in (weight..self.dp.len()).rev() {
39            if self.dp[i - weight] != i64::MIN {
40                self.dp[i] = self.dp[i].max(self.dp[i - weight] + value);
41            }
42        }
43    }
44    pub fn extend01<I>(&mut self, iter: I)
45    where
46        I: IntoIterator<Item = (i64, usize)>,
47    {
48        for (value, weight) in iter.into_iter() {
49            self.insert01(value, weight);
50        }
51    }
52    pub fn insert_limitation(&mut self, value: i64, weight: usize, count: usize) {
53        for i in 0..weight {
54            let mut deq = VecDeque::new();
55            let mut j = 0;
56            while j * weight + i < self.dp.len() {
57                if self.dp[j * weight + i] != i64::MIN {
58                    let v = self.dp[j * weight + i] - j as i64 * value;
59                    while deq.back().map(|&(_, x)| x <= v).unwrap_or_default() {
60                        deq.pop_back();
61                    }
62                    deq.push_back((j, v));
63                }
64                if let Some((l, v)) = deq.front() {
65                    self.dp[j * weight + i] = v + j as i64 * value;
66                    if l + count == j {
67                        deq.pop_front();
68                    }
69                }
70                j += 1;
71            }
72        }
73    }
74    pub fn extend_limitation<I>(&mut self, iter: I)
75    where
76        I: IntoIterator<Item = (i64, usize, usize)>,
77    {
78        for (value, weight, count) in iter.into_iter() {
79            self.insert_limitation(value, weight, count);
80        }
81    }
82    pub fn insert_limitation2(&mut self, value: i64, weight: usize, mut count: usize) {
83        let mut b = 1;
84        while count > 0 {
85            let k = b.min(count);
86            count -= k;
87            for i in (weight * k..self.dp.len()).rev() {
88                if self.dp[i - weight * k] != i64::MIN {
89                    self.dp[i] = self.dp[i].max(self.dp[i - weight * k] + value * k as i64);
90                }
91            }
92            b *= 2;
93        }
94    }
95    pub fn extend_limitation2<I>(&mut self, iter: I)
96    where
97        I: IntoIterator<Item = (i64, usize, usize)>,
98    {
99        for (value, weight, count) in iter.into_iter() {
100            self.insert_limitation2(value, weight, count);
101        }
102    }
103    pub fn solve(&self) -> Option<i64> {
104        self.dp.iter().filter(|&&dp| dp != i64::MIN).max().cloned()
105    }
106    pub fn get(&self, weight: usize) -> Option<i64> {
107        if self.dp[weight] != i64::MIN {
108            Some(self.dp[weight])
109        } else {
110            None
111        }
112    }
113}
114
115#[derive(Debug, Clone)]
116pub struct KnapsackPloblemSmallValue {
117    pub dp: Vec<i64>,
118}
119
120impl KnapsackPloblemSmallValue {
121    pub fn new(max_value: usize) -> Self {
122        let mut dp = vec![i64::MAX; max_value + 1];
123        dp[0] = 0;
124        Self { dp }
125    }
126    pub fn insert(&mut self, value: usize, weight: i64) {
127        for i in value..self.dp.len() {
128            if self.dp[i - value] != i64::MAX {
129                self.dp[i] = self.dp[i].min(self.dp[i - value] + weight);
130            }
131        }
132    }
133    pub fn extend<I>(&mut self, iter: I)
134    where
135        I: IntoIterator<Item = (usize, i64)>,
136    {
137        for (value, weight) in iter.into_iter() {
138            self.insert(value, weight);
139        }
140    }
141    pub fn insert01(&mut self, value: usize, weight: i64) {
142        for i in (value..self.dp.len()).rev() {
143            if self.dp[i - value] != i64::MAX {
144                self.dp[i] = self.dp[i].min(self.dp[i - value] + weight);
145            }
146        }
147    }
148    pub fn extend01<I>(&mut self, iter: I)
149    where
150        I: IntoIterator<Item = (usize, i64)>,
151    {
152        for (value, weight) in iter.into_iter() {
153            self.insert01(value, weight);
154        }
155    }
156    pub fn insert_limitation(&mut self, value: usize, weight: i64, mut count: usize) {
157        let mut b = 1;
158        while count > 0 {
159            let k = b.min(count);
160            count -= k;
161            for i in (value * k..self.dp.len()).rev() {
162                if self.dp[i - value * k] != i64::MAX {
163                    self.dp[i] = self.dp[i].min(self.dp[i - value * k] + weight * k as i64);
164                }
165            }
166            b *= 2;
167        }
168    }
169    pub fn extend_limitation<I>(&mut self, iter: I)
170    where
171        I: IntoIterator<Item = (usize, i64, usize)>,
172    {
173        for (value, weight, count) in iter.into_iter() {
174            self.insert_limitation(value, weight, count);
175        }
176    }
177    pub fn solve(&self, max_weight: i64) -> Option<usize> {
178        (0..self.dp.len())
179            .filter(|&i| self.dp[i] <= max_weight)
180            .max()
181    }
182    pub fn get(&self, value: usize) -> Option<i64> {
183        if self.dp[value] != i64::MAX {
184            Some(self.dp[value])
185        } else {
186            None
187        }
188    }
189}
190
191#[derive(Debug, Clone)]
192pub struct ZeroOneKnapsackProblemSmallItems {
193    a: Vec<(i64, i64)>,
194    b: Vec<(i64, i64)>,
195}
196
197impl Default for ZeroOneKnapsackProblemSmallItems {
198    fn default() -> Self {
199        Self {
200            a: vec![(0, 0)],
201            b: vec![(0, 0)],
202        }
203    }
204}
205
206impl ZeroOneKnapsackProblemSmallItems {
207    pub fn new() -> Self {
208        Default::default()
209    }
210    pub fn insert(&mut self, value: i64, weight: i64) {
211        let mut a_iter = self.a.iter().cloned();
212        let mut b_iter = self.a.iter().map(|&(v, w)| (v + value, w + weight));
213        let mut c = Vec::with_capacity(self.a.len() * 2);
214        let (mut a_next, mut b_next) = (a_iter.next(), b_iter.next());
215        loop {
216            match (a_next, b_next) {
217                (Some(a), Some(b)) => match a.1.cmp(&b.1) {
218                    Ordering::Less => {
219                        c.push(a);
220                        a_next = a_iter.next();
221                    }
222                    Ordering::Equal => {
223                        c.push((a.0.max(b.0), a.1));
224                        a_next = a_iter.next();
225                        b_next = b_iter.next();
226                    }
227                    Ordering::Greater => {
228                        c.push(b);
229                        b_next = b_iter.next();
230                    }
231                },
232                (None, Some(x)) | (Some(x), None) => {
233                    c.push(x);
234                    c.extend(a_iter);
235                    c.extend(b_iter);
236                    break;
237                }
238                (None, None) => {
239                    break;
240                }
241            }
242        }
243        self.a = c;
244        if self.a.len() > self.b.len() {
245            swap(&mut self.a, &mut self.b);
246        }
247    }
248    pub fn extend<I>(&mut self, iter: I)
249    where
250        I: IntoIterator<Item = (i64, i64)>,
251    {
252        for (value, weight) in iter.into_iter() {
253            self.insert(value, weight);
254        }
255    }
256    pub fn solve(&self, max_weight: i64) -> i64 {
257        let mut ans = 0;
258        let mut max = 0;
259        let mut i = 0;
260        for a in self.a.iter().rev() {
261            while i + 1 < self.b.len() && a.1 + self.b[i + 1].1 <= max_weight {
262                i += 1;
263                max = max.max(self.b[i].0);
264            }
265            if a.1 + self.b[i].1 <= max_weight {
266                ans = ans.max(a.0 + max);
267            }
268        }
269        ans
270    }
271}
272
273#[derive(Debug, Clone)]
274pub struct ZeroOneKnapsackPloblemBranchAndBound {
275    items: Vec<Item>,
276    gap: Item,
277}
278
279#[derive(Copy, Clone, Default, Debug)]
280struct Item {
281    value: i64,
282    weight: i64,
283}
284impl From<(i64, i64)> for Item {
285    fn from(vw: (i64, i64)) -> Self {
286        Self {
287            value: vw.0,
288            weight: vw.1,
289        }
290    }
291}
292impl Add for Item {
293    type Output = Self;
294    fn add(self, rhs: Self) -> Self::Output {
295        Self {
296            value: self.value + rhs.value,
297            weight: self.weight + rhs.weight,
298        }
299    }
300}
301impl Neg for Item {
302    type Output = Self;
303    fn neg(self) -> Self::Output {
304        Self {
305            value: -self.value,
306            weight: -self.weight,
307        }
308    }
309}
310impl ZeroOneKnapsackPloblemBranchAndBound {
311    pub fn new<I>(iter: I) -> Self
312    where
313        I: IntoIterator<Item = (i64, i64)>,
314    {
315        let mut items: Vec<Item> = iter.into_iter().map(From::from).collect();
316        let mut gap = Item::default();
317        for item in &mut items {
318            if item.weight < 0 {
319                gap = gap + *item;
320                *item = -*item;
321            }
322        }
323        items.sort_by(|i1, i2| {
324            (i2.value as i128 * i1.weight as i128, i2.value)
325                .cmp(&(i1.value as i128 * i2.weight as i128, i1.value))
326        });
327        Self { items, gap }
328    }
329    fn solve_relax(&self, i: usize, mut max_weight: i64) -> Result<i64, f64> {
330        let mut ans = 0i64;
331        for &Item { value, weight } in self.items[i..].iter() {
332            if max_weight == 0 {
333                break;
334            }
335            if weight <= max_weight {
336                max_weight -= weight;
337                ans += value;
338            } else {
339                return Err(ans as f64 + max_weight as f64 / weight as f64 * value as f64);
340            }
341        }
342        Ok(ans)
343    }
344    fn dfs(&self, i: usize, cur: Item, max_weight: i64, max_value: &mut i64) -> i64 {
345        if i == self.items.len() {
346            *max_value = cur.value.max(*max_value);
347            return cur.value;
348        }
349        match self.solve_relax(i, max_weight - cur.weight) {
350            Ok(relax) => {
351                *max_value = (relax + cur.value).max(*max_value);
352                return relax + cur.value;
353            }
354            Err(relax) => {
355                if *max_value as f64 > (relax + cur.value as f64) {
356                    return 0;
357                }
358            }
359        }
360        let mut ans = 0i64;
361        if cur.weight + self.items[i].weight <= max_weight {
362            ans = ans.max(self.dfs(i + 1, cur + self.items[i], max_weight, max_value));
363        }
364        ans.max(self.dfs(i + 1, cur, max_weight, max_value))
365    }
366    pub fn solve(&self, max_weight: i64) -> i64 {
367        self.dfs(
368            0,
369            Default::default(),
370            max_weight - self.gap.weight,
371            &mut 0i64,
372        ) + self.gap.value
373    }
374}
competitive/combinatorial_optimization/knapsack_problem.rs

competitive/combinatorial_optimization/
knapsack_problem.rs
