Rust 练习册：书店折扣与动态规划优化

文章摘要：本文探讨了书店折扣优化问题，针对购买《编程珠玑》系列丛书的不同分组策略进行计算。每本书原价8欧元，购买不同数量的书籍可获得5%-25%不等的折扣。通过动态规划算法和记忆化技术，实现了计算最低购书价格的解决方案。文章详细介绍了基础递归实现和优化后的动态规划版本，包括如何统计书籍数量、尝试不同分组方式，并利用哈希表存储中间结果以提高效率。该算法能有效处理复杂购书组合，找到最优折扣方案。

2501_94022858

617人浏览 · 2025-11-07 15:01:16

2501_94022858 · 2025-11-07 15:01:16 发布

在现实商业场景中，折扣策略是吸引顾客的重要手段。书店可能会为购买不同书籍的顾客提供不同的折扣，例如购买的书籍种类越多，折扣越大。在 Exercism 的 “book-store” 练习中，我们将解决一个有趣的优化问题：如何以最低的价格购买一组书籍。这不仅能帮助我们掌握动态规划算法，还能深入学习 Rust 中的集合操作和递归优化技巧。

问题描述

书店出售《编程珠玑》系列丛书，共有5卷。每本书的价格是8欧元（800欧分）。书店提供以下折扣：

买1本书：无折扣，每本8欧元
买2本不同的书：5%折扣，每本7.6欧元
买3本不同的书：10%折扣，每本7.2欧元
买4本不同的书：20%折扣，每本6.4欧元
买5本不同的书：25%折扣，每本6欧元

问题是：给定一个购物篮中的书籍列表，如何分组购买以获得最低总价？

让我们先看看练习提供的函数签名：

pub fn lowest_price(books: &[u32]) -> u32 {
    unimplemented!(
        "Find the lowest price of the bookbasket with books {:?}",
        books
    )
}

我们需要实现这个函数，它应该：

接收一个书籍列表（用数字1-5表示不同卷）
计算购买这些书籍的最低价格

算法分析

这个问题的关键在于找到最优的分组策略。例如，对于输入 [1, 1, 2, 2, 3, 3, 4, 5]，有两种分组方式：

一组5本不同书籍 + 一组3本不同书籍：
- 价格 = 30欧元（5本折扣25%）+ 21.6欧元（3本折扣10%）= 51.6欧元
两组4本不同书籍：
- 价格 = 25.6欧元（4本折扣20%）+ 25.6欧元（4本折扣20%）= 51.2欧元

显然，第二种分组方式更便宜。

基础实现

1. 计算价格函数

fn calculate_price(group_size: usize) -> u32 {
    let base_price = 800; // 每本书8欧元，以欧分为单位
    let discount = match group_size {
        1 => 0.0,
        2 => 0.05,
        3 => 0.10,
        4 => 0.20,
        5 => 0.25,
        _ => 0.0,
    };
    
    (base_price as f64 * group_size as f64 * (1.0 - discount)) as u32
}

2. 简单递归实现

use std::collections::HashMap;

pub fn lowest_price(books: &[u32]) -> u32 {
    if books.is_empty() {
        return 0;
    }
    
    // 统计每本书的数量
    let mut counts = [0; 6]; // 索引0未使用，1-5对应书籍卷号
    for &book in books {
        counts[book as usize] += 1;
    }
    
    // 只保留数量大于0的书籍
    let mut book_counts: Vec<u32> = counts.iter().skip(1).filter(|&&c| c > 0).cloned().collect();
    book_counts.sort_unstable();
    
    calculate_min_price(&book_counts)
}

fn calculate_min_price(book_counts: &[u32]) -> u32 {
    if book_counts.is_empty() {
        return 0;
    }
    
    let mut min_price = u32::MAX;
    
    // 尝试所有可能的分组大小（1到书籍种类数）
    for group_size in 1..=book_counts.len() {
        // 检查是否有足够的不同书籍来组成这个大小的组
        if book_counts.iter().filter(|&&count| count > 0).count() >= group_size {
            // 创建新状态：每种书籍数量减1（组成一个组）
            let mut new_counts = book_counts.to_vec();
            for i in 0..group_size {
                new_counts[new_counts.len() - 1 - i] -= 1;
            }
            
            // 清理0数量的书籍并重新排序
            new_counts.retain(|&count| count > 0);
            new_counts.sort_unstable();
            
            // 递归计算剩余书籍的最低价格
            let price = calculate_price(group_size) + calculate_min_price(&new_counts);
            min_price = min_price.min(price);
        }
    }
    
    if min_price == u32::MAX {
        0
    } else {
        min_price
    }
}

fn calculate_price(group_size: usize) -> u32 {
    let base_price = 800; // 每本书8欧元，以欧分为单位
    let discount = match group_size {
        1 => 0.0,
        2 => 0.05,
        3 => 0.10,
        4 => 0.20,
        5 => 0.25,
        _ => 0.0,
    };
    
    (base_price as f64 * group_size as f64 * (1.0 - discount)) as u32
}

优化实现（动态规划）

1. 使用记忆化优化

use std::collections::HashMap;

pub fn lowest_price(books: &[u32]) -> u32 {
    if books.is_empty() {
        return 0;
    }
    
    // 统计每本书的数量
    let mut counts = [0; 6]; // 索引0未使用，1-5对应书籍卷号
    for &book in books {
        counts[book as usize] += 1;
    }
    
    // 只保留数量大于0的书籍并排序
    let mut book_counts: Vec<u32> = counts.iter().skip(1).filter(|&&c| c > 0).cloned().collect();
    book_counts.sort_unstable();
    
    let mut memo = HashMap::new();
    calculate_min_price_memo(&book_counts, &mut memo)
}

fn calculate_min_price_memo(book_counts: &[u32], memo: &mut HashMap<Vec<u32>, u32>) -> u32 {
    if book_counts.is_empty() {
        return 0;
    }
    
    // 检查是否已经计算过这个状态
    if let Some(&price) = memo.get(book_counts) {
        return price;
    }
    
    let mut min_price = u32::MAX;
    
    // 尝试所有可能的分组大小（1到书籍种类数）
    for group_size in 1..=book_counts.len() {
        // 检查是否有足够的不同书籍来组成这个大小的组
        if book_counts.iter().filter(|&&count| count > 0).count() >= group_size {
            // 创建新状态：每种书籍数量减1（组成一个组）
            let mut new_counts = book_counts.to_vec();
            for i in 0..group_size {
                new_counts[new_counts.len() - 1 - i] -= 1;
            }
            
            // 清理0数量的书籍并重新排序
            new_counts.retain(|&count| count > 0);
            new_counts.sort_unstable();
            
            // 递归计算剩余书籍的最低价格
            let price = calculate_price(group_size) + calculate_min_price_memo(&new_counts, memo);
            min_price = min_price.min(price);
        }
    }
    
    let result = if min_price == u32::MAX { 0 } else { min_price };
    memo.insert(book_counts.to_vec(), result);
    result
}

fn calculate_price(group_size: usize) -> u32 {
    let base_price = 800; // 每本书8欧元，以欧分为单位
    let discount = match group_size {
        1 => 0.0,
        2 => 0.05,
        3 => 0.10,
        4 => 0.20,
        5 => 0.25,
        _ => 0.0,
    };
    
    (base_price as f64 * group_size as f64 * (1.0 - discount)) as u32
}

更高效的实现

1. 直接基于计数的实现

use std::collections::HashMap;

pub fn lowest_price(books: &[u32]) -> u32 {
    if books.is_empty() {
        return 0;
    }
    
    // 统计每本书的数量
    let mut counts = [0; 5];
    for &book in books {
        counts[(book - 1) as usize] += 1;
    }
    
    // 对计数进行排序
    counts.sort_unstable();
    
    let mut memo = HashMap::new();
    calculate_min_price(&counts, &mut memo)
}

fn calculate_min_price(counts: &[u32; 5], memo: &mut HashMap<[u32; 5], u32>) -> u32 {
    // 如果所有计数都是0，返回0价格
    if counts.iter().all(|&c| c == 0) {
        return 0;
    }
    
    // 检查记忆化
    if let Some(&cached) = memo.get(counts) {
        return cached;
    }
    
    let mut min_price = u32::MAX;
    
    // 尝试不同大小的组合（从大到小尝试，可能更快找到最优解）
    for group_size in (1..=5).rev() {
        // 检查是否有足够的书籍组成这个大小的组
        if counts[5 - group_size] > 0 {
            // 创建新的计数数组
            let mut new_counts = *counts;
            for i in (5 - group_size)..5 {
                new_counts[i] -= 1;
            }
            
            // 重新排序
            new_counts.sort_unstable();
            
            let price = calculate_price(group_size) + calculate_min_price(&new_counts, memo);
            min_price = min_price.min(price);
        }
    }
    
    let result = min_price;
    memo.insert(*counts, result);
    result
}

fn calculate_price(group_size: usize) -> u32 {
    const BOOK_PRICE: u32 = 800;
    let discount = match group_size {
        1 => 0.0,
        2 => 0.05,
        3 => 0.10,
        4 => 0.20,
        5 => 0.25,
        _ => 0.0,
    };
    
    (BOOK_PRICE as f64 * group_size as f64 * (1.0 - discount)) as u32
}

测试用例分析

通过查看测试用例，我们可以更好地理解需求：

#[test]
/// Only a single book
fn test_only_a_single_book() {
    process_total_case((vec![1], vec![vec![1]]), 800);
}

单本书无折扣，价格为800欧分（8欧元）。

#[test]
/// Two different books
fn test_two_different_books() {
    process_total_case((vec![1, 2], vec![vec![1, 2]]), 1_520);
}

两本不同书籍享受5%折扣，每本7.6欧元，总价15.2欧元（1520欧分）。

#[test]
/// Two groups of four is cheaper than group of five plus group of three
fn test_two_groups_of_four_is_cheaper_than_group_of_five_plus_group_of_three() {
    process_total_case(
        (
            vec![1, 1, 2, 2, 3, 3, 4, 5],
            vec![vec![1, 2, 3, 4], vec![1, 2, 3, 5]],
        ),
        5_120,
    );
}

这个测试用例展示了优化的重要性：两组4本书（每组享受20%折扣）比一组5本加一组3本更便宜。

性能优化版本

考虑性能的进一步优化实现：

use std::collections::HashMap;

pub fn lowest_price(books: &[u32]) -> u32 {
    if books.is_empty() {
        return 0;
    }
    
    // 统计每本书的数量（针对5卷系列进行优化）
    let mut counts = [0u32; 5];
    for &book in books {
        if book >= 1 && book <= 5 {
            counts[(book - 1) as usize] += 1;
        }
    }
    
    // 对计数进行排序以获得规范形式
    counts.sort_unstable();
    
    // 使用静态记忆化以避免重复计算
    thread_local! {
        static MEMO: std::cell::RefCell<HashMap<[u32; 5], u32>> = 
            std::cell::RefCell::new(HashMap::new());
    }
    
    MEMO.with(|memo| {
        let mut memo_ref = memo.borrow_mut();
        calculate_min_price(&counts, &mut memo_ref)
    })
}

fn calculate_min_price(counts: &[u32; 5], memo: &mut HashMap<[u32; 5], u32>) -> u32 {
    // 如果所有计数都是0，返回0价格
    if counts.iter().all(|&c| c == 0) {
        return 0;
    }
    
    // 检查记忆化
    if let Some(&cached) = memo.get(counts) {
        return cached;
    }
    
    let mut min_price = u32::MAX;
    
    // 从最大的可能组开始尝试（贪心策略）
    for group_size in (1..=5).rev() {
        // 检查是否有足够的书籍组成这个大小的组
        // 由于counts已排序，前(5-group_size)个元素应该是0
        if counts[5 - group_size] > 0 {
            // 创建新的计数数组
            let mut new_counts = *counts;
            // 从最大的计数开始减少（因为已排序）
            for i in (5 - group_size)..5 {
                new_counts[i] -= 1;
            }
            
            // 重新排序以保持规范形式
            new_counts.sort_unstable();
            
            let price = calculate_price(group_size) + calculate_min_price(&new_counts, memo);
            min_price = min_price.min(price);
        }
    }
    
    let result = if min_price == u32::MAX { 0 } else { min_price };
    memo.insert(*counts, result);
    result
}

fn calculate_price(group_size: usize) -> u32 {
    const BOOK_PRICE: u32 = 800;
    match group_size {
        1 => BOOK_PRICE,
        2 => (BOOK_PRICE as f64 * 0.95 * 2.0) as u32, // 5%折扣
        3 => (BOOK_PRICE as f64 * 0.90 * 3.0) as u32, // 10%折扣
        4 => (BOOK_PRICE as f64 * 0.80 * 4.0) as u32, // 20%折扣
        5 => (BOOK_PRICE as f64 * 0.75 * 5.0) as u32, // 25%折扣
        _ => 0,
    }
}

错误处理和边界情况

考虑边界情况的实现：

use std::collections::HashMap;

pub fn lowest_price(books: &[u32]) -> u32 {
    // 处理空输入
    if books.is_empty() {
        return 0;
    }
    
    // 验证输入（书籍编号应在1-5范围内）
    if books.iter().any(|&book| book < 1 || book > 5) {
        // 根据题目要求，可能应该返回错误，但函数签名不允许
        // 这里我们选择忽略无效书籍
        return 0;
    }
    
    // 统计每本书的数量
    let mut counts = [0u32; 5];
    for &book in books {
        counts[(book - 1) as usize] += 1;
    }
    
    // 对计数进行排序
    counts.sort_unstable();
    
    let mut memo = HashMap::new();
    calculate_min_price(&counts, &mut memo)
}

fn calculate_min_price(counts: &[u32; 5], memo: &mut HashMap<[u32; 5], u32>) -> u32 {
    // 基本情况：所有计数都是0
    if counts.iter().all(|&c| c == 0) {
        return 0;
    }
    
    // 检查记忆化
    if let Some(&cached) = memo.get(counts) {
        return cached;
    }
    
    let mut min_price = u32::MAX;
    
    // 尝试所有可能的组大小
    for group_size in 1..=5 {
        // 检查是否可以组成这个大小的组
        if counts[5 - group_size] > 0 {
            // 创建新状态
            let mut new_counts = *counts;
            for i in (5 - group_size)..5 {
                if new_counts[i] > 0 {
                    new_counts[i] -= 1;
                }
            }
            
            // 重新排序
            new_counts.sort_unstable();
            
            // 递归计算
            let price = calculate_price(group_size) + calculate_min_price(&new_counts, memo);
            min_price = min_price.min(price);
        }
    }
    
    let result = min_price;
    memo.insert(*counts, result);
    result
}

fn calculate_price(group_size: usize) -> u32 {
    const BOOK_PRICE: u32 = 800;
    match group_size {
        1 => BOOK_PRICE,
        2 => (BOOK_PRICE as f64 * 1.90) as u32,   // 2 * (1 - 0.05)
        3 => (BOOK_PRICE as f64 * 2.70) as u32,   // 3 * (1 - 0.10)
        4 => (BOOK_PRICE as f64 * 3.20) as u32,   // 4 * (1 - 0.20)
        5 => (BOOK_PRICE as f64 * 3.75) as u32,   // 5 * (1 - 0.25)
        _ => 0,
    }
}

实际应用场景

书店折扣问题在实际开发中有以下应用：

电商折扣系统：实现复杂的购物车折扣逻辑
资源分配：优化资源分组以最小化成本
任务调度：将任务分组以优化执行效率
库存管理：优化库存组合以减少成本

算法复杂度分析

时间复杂度：O(n₁ × n₂ × n₃ × n₄ × n₅)，其中 nᵢ 是第i种书籍的数量
- 由于最多只有5种书籍，且每种书籍数量有限，实际运行时间是可接受的
- 通过记忆化避免重复计算
空间复杂度：O(n₁ × n₂ × n₃ × n₄ × n₅)
- 主要用于存储记忆化表

与其他算法的比较

// 贪心算法（不总是最优）
pub fn lowest_price_greedy(books: &[u32]) -> u32 {
    if books.is_empty() {
        return 0;
    }
    
    let mut counts = [0u32; 5];
    for &book in books {
        counts[(book - 1) as usize] += 1;
    }
    
    let mut total = 0;
    while counts.iter().any(|&c| c > 0) {
        let group_size = counts.iter().filter(|&&c| c > 0).count();
        total += calculate_price(group_size);
        
        // 减少计数
        counts.sort_unstable(); // 确保0在前面
        for i in (5 - group_size)..5 {
            if counts[i] > 0 {
                counts[i] -= 1;
            }
        }
    }
    
    total
}

// 穷举算法（指数时间复杂度）
pub fn lowest_price_brute_force(books: &[u32]) -> u32 {
    // 这种方法对于大输入是不可行的
    // 仅用于小规模输入或演示目的
    unimplemented!("Brute force approach is too slow for practical use")
}

总结

通过 book-store 练习，我们学到了：

动态规划：掌握了使用记忆化优化递归算法的技巧
状态表示：学会了如何有效地表示和转换问题状态
优化策略：理解了贪心算法与动态规划的区别
集合操作：熟练使用数组和哈希表进行数据统计
边界处理：学会了处理各种边界情况
性能优化：了解了记忆化和状态规范化等优化技巧

这些技能在实际开发中非常有用，特别是在实现复杂的业务逻辑、优化资源分配和解决组合优化问题时。书店折扣问题虽然看起来简单，但它涉及到了动态规划、状态搜索和优化算法等许多核心概念，是学习 Rust 算法实现的良好起点。

通过这个练习，我们也看到了 Rust 在算法实现方面的强大能力，以及如何用安全且高效的方式表达复杂的优化逻辑。这种结合了安全性和性能的语言特性正是 Rust 的魅力所在。

旋武技术社区

开放原子旋武开源社区由开放原子开源基金会孵化及运营，业务方向涉及操作系统、终端设备、安全技术、基础软件等关键领域，致力于推动Rust编程语言在中国的开源生态建设与产业落地，面向开发者全面宣传和推广Rust。

更多推荐

RustFS vs MinIO：谁才是国产高性能对象存储之光？

旋武技术社区

Rust探索之旅·开发者技术创作征文活动获奖名单正式公布

当高性能与内存安全成为技术研发的核心追求，Rust 语言正以其独特优势席卷多领域开发场景。由旋武社区主理人发起，CSDN 与 GitCode 联合举办的 “Rust 探索之旅・开发者技术创作征文活动” 已圆满落幕。活动期间，全国各地的 Rust 技术爱好者踊跃参与，围绕语言特性、开源库应用、实战项目复盘等核心方向创作了大量优质内容，既展现了 Rust 生态的蓬勃活力，也为开发者群体搭建了高效的技术