hdu 2069

末蓝、 2023-02-28 05:25 22阅读 0赞

![博客图片][format_png]

## 最少硬币组合问题 ##

给出 n n n中硬币面值,不限定硬币的数量,计算某个金额所需的最下的硬币的数量.对应的递推方程如下: M i n ( x ) = min ⁡ \{ M i n ( x ) , M i n ( x − v ( i ) ) + 1 \} Min(x) = \\min \\\{Min(x),Min(x-v(i))+1\\\} Min(x)=min\{ Min(x),Min(x−v(i))\+1\}.`Min(x)`表示金额为`x`的硬币所需的最小的数量,`v(i)`表示第`i`中硬币的面值.

这里面没有对硬币的数量进行限制,那如果对硬币的数量添加一些限制,有该怎么解决?再添加一些其他条件呢,比如某个两种硬币不能同时使用?用贪心能不能解决这类最小硬币组合问题?

## 打印最小硬币组合的方案 ##

为了输出最小硬币组合的的方案,需要一个额外的数据记录最后一次选择的硬币的种类.假设`Path[x]`记录的是金额为 x x x时需要的最后一枚硬币的种类,其值为`v[i]`,那么可以根据`Path[x-v[i]]`找到倒数第二枚硬币的种类`v[j]`,重复执行,直到`x-v[i]`的值为`0`.

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N = 1000;
    const int M = 5;
    ll Min[N];
    ll Path[N];
    const int values[] = {
        1, 5, 10, 20, 50};
    
    void solve(){
        
        fill(Min, Min + N,N+1);
        memset(Path, 0, sizeof(Path));
        Min[0] = 0;
        for (int i = 0;i < N; ++i){
        
            for (int j = 0; j < M; ++j){
        
                if( i >= values[j]){
        
                    if( Min[i] > Min[i-values[j]]+1){
        
                        Min[i] = Min[i - values[j]] + 1;
                        Path[i] = values[j];
                    }
                }
            }
        }
    }

## 打印所有的硬币组合方案 ##

给出集中硬币,计算某种金额可能的组合方案数目.

### 硬币数量没有限制 ###

void solve(){
        
        dp[0] = 1;
        for (int i = 0; i < M; ++i){
        
            for (int j = values[i]; j < N; ++j){
        
                dp[j] += dp[j - values[i]];
            }
        }
    }

先计算每种金额使用第一种硬币的数目,再将每种金额使用第二种的硬币的方法数加到前一种.注意这里面因为每种金额的数量是依赖于前面的的方法数`dp[j] += dp[j-values[i]]`,`dp[j]`使用`1`种面额为`values[i]`的硬币,那么要将`dp[j-values[i]]`可能的方法数加入到`dp[j]`中,而`dp[j-values[i]]`也可能使用了`values[j]`这种硬币也可能没用,所以`dp[j]`的每一轮就散依赖于前一轮计算更新的结果,并且本轮更新的结果会影响下一轮,所以遍历所有金额的循环放在了内层,遍历金额数目的放在了外层,因为这个要找到所有解;而前面那个找最优解的遍历所有金额的放在外层,遍历金额的放在内层,也就是经过一轮内层循环一定可以找到该金额的最优解,并且该金额的最优解依赖于前面的最优解.尤其注意着两种循环结构的区别.一个是最优解,经过一轮内层循环就可以计算出来,一个是所有解,需要不断更新所有金额的解的数量.

## 使用的硬币总数有限制 ##

这时要在原来的`dp`数组上多加一个数量限制,特别地,当`i!=0`时,`dp[i][0]=1`,从而可以处理由于硬币数量超限,额没法构成一种组合方案,对原来的方法稍加变换可以得到一个`dp[i][j]`,使用`j`枚硬币,可以构成`i`金额的方法数,如果要求最多使用硬币数量,要对应的进行一个累加.

void solve() {
        
        dp[0][0] = 1;
        for (int i = 0; i < M; ++i){
        
            for (int j = 1; j < nums; ++j){
        
                for (int k = values[i]; k < N; ++k){
        
                    dp[k][j] += dp[k - values[i]][j - 1];
                }
            }
        }
        for (int i = 0; i < N; ++i){
        
            for (int j= 0; j < nums; ++j){
        
                ans[i] += dp[i][j];
            }
        }
    }

#### 题目链接 ####

[hdu2069][]

[format_png]: /images/20230209/265ff381ef314a46b1a720acf3f9f00b.png
[hdu2069]: http://acm.hdu.edu.cn/showproblem.php?pid=2069