dp算法之硬币找零问题
作者: / 2019-07-31 / 浏览次数:

设所需硬币最小数目为m,则可以看出m[ i ][  j ]=m[ i-1 ][  j-k*p[ i ]] + k.其中k*p[ i ] =j.确切的说,k=j/p[ i ].

dp算法的显著特征之一就是具有最优子结构,且这一状态的最优解与上一状态的最优解有关。写出状态方程之后我们就可以开始具体处理代码了。

 1 #include iostream 
 2 using namespace std;
 3 int main
 5 int i, j, k;
 6 int m, n;//m就是总值
 7 cout "总数:" endl;
 8 cin m;
 9 //m = 10, ;
10 n = 3;
11 int **c = new int *[n + 1];
12 for 
14 c[i] = new int[m + 1];
16 int p[4] = { 0,1,3,5 };
17 for 
19 for 
21 c[i][j] = 0;//初始化
24 for 
26 for 
28 k = j / p[i];
29 c[i][j] = c[i - 1][j - k * p[i]] + k;
32 for 
34 for 
36 cout c[i][j] " ";
38 cout endl;
40 return 0;
41 }

分析:这个硬币找零问题在dp算法中比较经典,复杂度低于经典的背包问题,因为背包问题还要考虑 k 的值,需要遍历 k 的值来找到一个最优解,此题不需要。

结果:

下一篇将要分析经典的背包问题了,包括01背包、完全背包、多重背包。

 

【某某业务】网站建设、网站设计、服务器空间租售、网站维护、网站托管、网站优化、百度推广、自媒体营销、微信公众号
如有意向---联系我们
热门栏目
热门资讯

网站建设 网站托管 成功案例 新闻动态 关于我们 联系我们 服务器空间 加盟合作 网站优化

备案号: 

公司地址:江苏省南京市玄武区玄武湖 咨询QQ:9490489 手机: 电话: