426-动态规划算法-硬币选择问题

小咪咪 2022-09-05 04:24 131阅读 0赞

## 硬币选择问题 ##

**硬币选择问题：有1，3，5分面额的硬币，给定一个面值11，问组成给定面值所需要的最少的硬币数量是多少？？？**

## 我们先用分治算法解决 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
![在这里插入图片描述][6dd2b38cef5d4a6897d061f86c196a4d.png]

## 递归版本的动态规划算法 ##

**我们知道：**  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]

#include <iostream>
    #include <algorithm>
    using namespace std;
    
    //参数n表示面值， 返回值表示组成面值n所需要的最少的硬币数量
    const int n = 100;
    int dp[n + 1] = {
         0 };//dp[n] : 组成价值n需要的硬币最少数量
    int cnt = 0;//代码测试
    
    int func1(int n) 
    {
        
    	if (dp[n] > 0) 
    	{
          //表示dp[n]这个子问题已经被求解过了
    		cnt++;
    		return dp[n];//直接返回就可以了
    	}
    	if (n == 1 || n == 3 || n == 5) 
    	{
        
    		dp[n] = 1;//代表了一个子问题最优解的性质（或者说状态）
    		return 1;
    	}
    	else if (n == 2 || n == 4)
    	{
        
    		dp[n] = 2;//代表了一个子问题最优解的性质（或者说状态）
    		return 2;
    	}
    	else 
    	{
        
    		int n1 = func1(n-1) + 1;//选择了1分硬币
    		int n2 = func1(n-3) + 1;//选择了3分硬币
    		int n3 = func1(n - 5) + 1;//选择了5分硬币
    		dp[n] = std::min({
         n1, n2, n3 });
    		return dp[n];//把子问题的状态记录在dp中 
    		//return std::min(std::min(n1, n2), n3);
    	}
    }

![在这里插入图片描述][fd13bc1c24df4012a09c9ebc3e3c9269.png]  
**如果使用分治算法，子问题被重复求解了186次**

## 非递归版本的动态规划算法 ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]

int main()
    {
        
        //非递归的动态规划算法如下： 
    	int v[] = {
         1,3,5 };//硬币的面值
    	int length = sizeof(v) / sizeof(v[0]);//硬币的个数
    	int c = 18;
    	int *dp = new int[c + 1]();//因为要访问dp[c] ，dp[0] = 0
    	for (int i = 1; i <= c; ++i) 
    	{
        
    		dp[i] = i;//表示初始化全部由1分硬币组成，这个选择的数量肯定是最多的
    		for (int j = 0; j < length; ++j)//遍历硬币数组
    		{
        
    			if (i >= v[j] && (1 + dp[i - v[j]]) < dp[i])//面值大于等于硬币的面额 ，而且发现有更优的值
    			{
        
    				dp[i] = 1 + dp[i - v[j]];//更新最优值
    			}
    		}
    	}
    
    	cout << dp[c] << endl;
    	delete[]dp;
    
    	return 0;
    }

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

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/8bd4117d11c64a59aad7e71f3e38e8a1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70]: /images/20220829/559816c9724a4f77a6cd74404908d822.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/e98bf4c1516441f0ba16da25392ee666.png
[6dd2b38cef5d4a6897d061f86c196a4d.png]: /images/20220829/d041b4035900446d9b13ff9637cf5892.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/3a3e71c1e9bf4458844ff793a4ca7559.png
[fd13bc1c24df4012a09c9ebc3e3c9269.png]: /images/20220829/1e26f832217e4443b4c41f761e9d3b78.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBALeael-azveWuhw_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/a022692cf2c1471a907d0cae880053ed.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0xJTlpFWVU2NjY_size_16_color_FFFFFF_t_70 1]: /images/20220829/1e6743d69f1a4a7ea2099f9764ab4380.png