背包DP | 找零钱问题

浅浅的花香味﹌ 2023-07-19 10:34 13阅读 0赞

> **找零钱问题：**假设有一个出纳员手中有几种面值的硬币，要求他用**最少的硬币数支付规定的现金**。例如，现有3种硬币：它们的面值分别为1元、4元和6元。要支付8元。

--------------------

找零钱问题可以使用贪心或完全背包来解决，但是用贪心解决是对面值的数字有条件的，不是所有的情况都可以的。具体的区别可以看看这篇文章：[最优找零问题 —— 贪心or动态规划][_ _or]，写的很清楚 。本文是根据 [背包DP | 完全背包问题][DP _] 模型来解决问题。

本题完全可以转化为 ：货币种类数 n = 3，各价值为 c\[3\] = \{1,4,6\}，各重量均为 1。求 V = 8 的背包装满所需要的最小重量。dp\[ i \]\[ j \]：用前i种货币支付 j 元的最小货币量，**状态转移方程**如下：

**情况1：**![j < c\[i\]][j _ c_i]

![dp\[i\]\[j\] = dp\[i-1\]\[j\]][dp_i_j_ _ dp_i-1_j]

**情况2**：![j \\geq c\[i\]][j _geq c_i]

*  当 ![1\\leq i\\leq n][1_leq i_leq n] 且 ![1\\leq j\\leq V][1_leq j_leq V]：![\\bg\_white dp\[i\]\[j\] = min(dp\[i-1\]\[j\], dp\[i\]\[j-c\[i\]\] + 1)][bg_white dp_i_j_ _ min_dp_i-1_j_ dp_i_j-c_i_ _ 1]

**初始条件**：

*  dp\[ 0 \]\[ j \] = ∞
 *  dp\[ i \]\[ 0 \] = 0

--------------------

**代码实现 **

int solve(int n, int v, int c[]) {
        /* 赋予初值 */
        int dp[MAXN][MAXV] = {0};
        for (int j = 1; j < MAXV; j++)
            dp[0][j] = INT_MAX;
    
        for (int i = 1; i <= n; i++)  //i为当前可选货币
            for (int j = 1; j <= v; j++) {  //j为最大容量
                if (c[i] > j)
                    dp[i][j] = dp[i - 1][j];
                else
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - c[i]] + 1);
            }
        return dp[n][v];
    }
    
    int main() {
        int n = 3;
        int c[4] = {0, 1, 4, 6};
        printf("%d\n", solve(n, 19, c));
    }

--------------------

**有任何问题欢迎评论交流，如果本文对您有帮助不妨点点赞，嘻嘻~ **

--------------------

# end  #

欢迎关注个人公众号**“** **鸡翅编程 ”**，这里是认真且乖巧的码农一枚。

*---- 做最乖巧的博客er，做最扎实的程序员 ----*

旨在用心写好每一篇文章，平常会把笔记汇总成推送更新~

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]

[_ _or]: https://blog.csdn.net/jal517486222/article/details/83787279?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522158554788219724811826455%2522%252C%2522scm%2522%253A%252220140713.130056874..%2522%257D&request_id=158554788219724811826455&biz_id=0&utm_source=distribute.pc_search_result.none-task
[DP _]: https://blog.csdn.net/weixin_43787043/article/details/105197709
[j _ c_i]: https://private.codecogs.com/gif.latex?%5Cbg_white%20j%20%3C%20c%5Bi%5D
[dp_i_j_ _ dp_i-1_j]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Bi%5D%5Bj%5D%20%3D%20dp%5Bi-1%5D%5Bj%5D
[j _geq c_i]: https://private.codecogs.com/gif.latex?%5Cbg_white%20j%20%5Cgeq%20c%5Bi%5D
[1_leq i_leq n]: https://private.codecogs.com/gif.latex?%5Cbg_white%201%5Cleq%20i%5Cleq%20n
[1_leq j_leq V]: https://private.codecogs.com/gif.latex?%5Cbg_white%201%5Cleq%20j%5Cleq%20V
[bg_white dp_i_j_ _ min_dp_i-1_j_ dp_i_j-c_i_ _ 1]: https://private.codecogs.com/gif.latex?%5Cbg_white%20dp%5Bi%5D%5Bj%5D%20%3D%20min%28dp%5Bi-1%5D%5Bj%5D%2C%20dp%5Bi%5D%5Bj-c%5Bi%5D%5D%20&plus;%201%29
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzc4NzA0Mw_size_16_color_FFFFFF_t_70]: /images/20230528/c5a7141223a24b5aa6db4d651a1c143b.png