如何将Rust整数版最小硬币找零算法改为支持浮点数？

编写一个函数，返回使用给定硬币面额凑出目标金额所需的最少硬币数量。我正尝试将基于i32的整数版解决方案修改为支持浮点数（如0.5、1.5、2.0这类小数面额）的版本，但直接替换类型后出现了编译错误，希望得到解决方法。

整数版Rust代码 #

use std::cmp;

fn min_number_of_change(n: i32, denoms: Vec<u32>) -> i32 {
    let mut ways: Vec<i32> = vec![i32::MAX;n as usize + 1];
    ways[0] = 0;

    for denom in denoms.iter() {
        for current in 0..ways.len() {
            if *denom <= current as u32 {
                ways[current as usize] = cmp::min(ways[current as usize], 1 + ways[current as usize - *denom as usize]) 
                                  
            }
        }
    }
    if ways[n as usize] != i32::MAX {
        ways[n as usize]
    } else {
          -1
    }
}
fn main() {
    let denoms: Vec<u32> = vec![1, 5, 10, 2, 3];
    let n: i32 = 6;

    let result: i32 = min_number_of_change(n, denoms);
    println!("Result: {}", result);
}

我的尝试与问题 #

我直接将i32替换为f32，使用f32的min函数比较，但编译时出现类型不匹配错误：无法从usize中减去f32，且[f32]类型不能用f32索引。尝试代码如下：

fn min_number_of_change(n: f32, denoms: Vec<f32>) -> f32 {
    let mut ways: Vec<f32> = vec![f32::INFINITY; n + 1.0];
    ways[0] = 0.0;

    for denom in denoms.iter() {
        for current in 0..ways.len() {
            if *denom <= current {
                ways[current] = (ways[current].min(1 + ways[current  - *denom ]), 1 + ways[current  - *denom ])
            }
        }
    }
    if ways[n] != f32::INFINITY {
        ways[n]
    } else {
        -1.0
    }
}


fn main() {
    let denoms: Vec<f32> = vec![2.00, 1.00, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01];
    let n: f32 = 4.55;

    let result: f32 = min_number_of_change(n, denoms);
    println!("Result: {}", result);
}

解决方案 #

直接使用浮点数处理存在两个核心问题：一是浮点数精度误差（比如0.1在二进制中无法精确表示，会导致金额计算偏差）；二是动态规划数组的索引必须是整数，无法用浮点数直接索引。

正确的做法是将所有金额转换为整数单位（比如把元转成分，乘以100），复用整数版的动态规划逻辑，处理完成后再按需转换回原单位。具体实现如下：

use std::cmp;

// 处理浮点数版本的最少硬币找零，通过转换为整数避免精度与类型问题
fn min_number_of_change_float(target: f64, denoms: Vec<f64>) -> i32 {
    // 确定转换倍率，这里假设所有面额的小数位数不超过2位（如元→分）
    let multiplier = 100.0;

    // 将目标金额和面额转换为整数，用round处理浮点数精度误差
    let target_int = (target * multiplier).round() as i32;
    let denoms_int: Vec<u32> = denoms.iter()
        .map(|&d| (d * multiplier).round() as u32)
        .collect();

    // 复用整数版动态规划逻辑
    let mut ways: Vec<i32> = vec![i32::MAX; target_int as usize + 1];
    ways[0] = 0;

    for &denom in &denoms_int {
        for current in 0..ways.len() {
            if denom <= current as u32 {
                let prev_idx = current as usize - denom as usize;
                // 仅当前置状态可达时才更新，避免溢出
                if ways[prev_idx] != i32::MAX {
                    ways[current] = cmp::min(ways[current], 1 + ways[prev_idx]);
                }
            }
        }
    }

    if ways[target_int as usize] != i32::MAX {
        ways[target_int as usize]
    } else {
        -1
    }
}

fn main() {
    let denoms: Vec<f64> = vec![2.00, 1.00, 0.50, 0.20, 0.10, 0.05, 0.02, 0.01];
    let target: f64 = 4.55;

    let result = min_number_of_change_float(target, denoms);
    println!("最少硬币数量: {}", result);
}

关键说明 #

• 精度处理：使用round()方法转换整数，避免因二进制浮点精度问题导致的转换错误（比如0.1实际存储为0.10000000149...，乘以100后round为10）。
• 类型兼容：转换为整数后，完全复用原有的动态规划逻辑，规避了浮点数索引和运算的类型冲突。
• 扩展性：如果需要支持更多小数位数（比如3位），只需调整multiplier为1000即可。

内容的提问来源于stack exchange，提问作者Captain