01 背包问题，简单记录。

0-1 背包

image

数学表达式

  • 总价值：$V$ for Value
  • 背包容量：$W$ for MaxWeight
  • 包裹重量与价值分别为：$w_i$ 和 $v_i$

求解 n 个包裹，使得 $sum(w_i) < W$ 的前提下，即

\[\sum_{i=0}^n w_i x_i < W\]

使得 $V$ 最大

\[V(x) = \sum_{i=0}^n v_i x_i\]

对于第 $i$ 个包裹，背包容量为 $W$ 的最大 $V$，有以下公式

\[V(i, W) = \begin{cases} V(i - 1, W) &\text { if \( w_i > W\)} \\ max\{V(i - 1, W), V(i - 1, W - w_i) + v_i\} &\text { else \(w_i <= W\)} \end {cases}\]
  • $V(i - 1, W)$ 为不放第 $i$ 个包裹
  • $V(i - 1, W - w_i) + v_i$ 为放第 $i$ 个包裹到背包中
  • $max{f_1, f_2}$ 为取两个函数中最大的
  • 当 $i$ 为 1 的时候，显然有
\[V(1, W) = \begin{cases} 0 &\text { if \( w_1 > W\)} \\ max\{0, 0 + v_1\} = v_1 &\text { else \(w_1 <= W\)} \end {cases}\]

JS 非优化版本

去除计算缓存，去除结构定义等。主要用于梳理逻辑。

const packages = [
  { weight: 2, value: 6 },
  { weight: 2, value: 3 },
  { weight: 6, value: 5 },
  { weight: 5, value: 4 },
  { weight: 4, value: 6 }
]

function calculateValue (i, w) {
  if (i < 0) return 0

  if (packages[i].weight > w) {
    return calculateValue(i - 1, w)
  }
  return Math.max(
    calculateValue(i - 1, w),
    calculateValue(i - 1, w - packages[i].weight) + packages[i].value
  )
}

const maxValue = calculateValue(packages.length - 1, 10)
console.log(maxValue)

Rust 优化版本

主要用于学习 rust。

use std::cmp;
use std::collections::HashMap;

struct Package {
    weight: i32,
    value: i32,
}

const PACKAGES: [Package; 5] = [
    Package {
        weight: 2,
        value: 6,
    },
    Package {
        weight: 2,
        value: 3,
    },
    Package {
        weight: 6,
        value: 5,
    },
    Package {
        weight: 5,
        value: 4,
    },
    Package {
        weight: 4,
        value: 6,
    },
];

/**
 * 计算最大值
 * i 第几个
 * w 当前空间
 * cache 用于缓存递归中的值
 */
fn calculate_value(i: i32, w: i32, cache: &mut HashMap<(i32, i32), i32>) -> i32 {
    if i < 0 {
        return 0;
    }

    // 命中递归缓存的，直接返回已经计算好的最大值
    let cache_result = cache.get(&(i, w));
    if !cache_result.is_none() {
        return *cache_result.unwrap();
    }

    let current_value: i32;

    // 递归
    if PACKAGES[i as usize].weight > w {
        current_value = calculate_value(i - 1, w, cache);
    } else {
        current_value = cmp::max(
            calculate_value(i - 1, w, cache),
            calculate_value(i - 1, w - PACKAGES[i as usize].weight, cache) +
                PACKAGES[i as usize].value
        );
    }

    // 添加缓存
    let _ = &cache.insert((i, w), current_value);
    return current_value;
}

fn main() {
    let mut cache: HashMap<(i32, i32), i32> = HashMap::new();
    let max_value: i32 = calculate_value((PACKAGES.len() - 1) as i32, 10, &mut cache);
    println!("max_value {:?}", max_value);

    for entry in cache.into_iter() {
        println!("i:{}\t w:{}\t = v:{}", entry.0.0, entry.0.1, entry.1)
    }
}

Reference