江苏龙网

  1. 首页 > 生活 > >

动态规划和贪心法的区别( 四 )


}
} else {
break;
}
}
// 保存最小硬币数
minCoins = min;

System.out.println("面值为 " + (sum) + " 的最小硬币数 : " + minCoins);
}
}

public static void main(String args) {

// 硬币面值预先已经按升序排列
int coinValue = https://www.zhihu.com/api/v4/questions/265770250/new int {1,5,11};
\t\t// 需要的金额(15用动态规划得到的是3（5+5+5），用贪心得到的是5（11+1+1+1+1）
int money = 15;
// 保存每一个金额所需的最小硬币数，0号单元舍弃不用，所以要多加1
int coinsUsed = new int;

dp(coinValue, money, coinsUsed);
}
}
```

运行结果：
```
面值为1的最小硬币数：1
面值为2的最小硬币数：2
面值为3的最小硬币数：3
面值为4的最小硬币数：4
面值为5的最小硬币数：1
面值为6的最小硬币数：2
面值为7的最小硬币数：3
面值为8的最小硬币数：4
面值为9的最小硬币数：5
面值为10的最小硬币数：2
面值为11的最小硬币数：1
面值为12的最小硬币数：2
面值为13的最小硬币数：3
面值为14的最小硬币数：4
面值为15的最小硬币数：3
```


#三、贪心算法与动态规划的区别
（1）贪心是求局部最优，但不定是全局最优。若想全局最优，必须证明。
dp是通过一些状态来描述一些子问题，然后通过状态之间的转移来求解。般只要转移方程是正确的，答案必然是正确的。

（2）动态规划本质上是穷举法，只是不重复计算罢了。结果是最优的。复杂度高。
贪心算法不一定最优。复杂度一般较低。

（3）贪心只选择当前最有利的，不考虑这步选择对以后的选择造成的影响，眼光短浅，不能看出全局最优；动规是通过较小规模的局部最优解一步步最终得出全局最优解。

（4）从推导过程来看，动态规划是贪心的泛化，贪心是动态规划的特例


■网友
首先，谢邀…… //按照体好像是要这样这个区别的话，举例子比较好说明吧：有1，3，4面值的硬币各无数；贪心：拿三个硬币，要最多的钱；dp：拿六块钱，要最少的硬币数；贪心就直接从最大面值下手，直到拿完三个硬币；而dp需要一步步分析：拿一块钱最少的硬币数，然后推出拿两块最少的硬币数……一直递推到六块可以的最少硬币数；一般来说，贪心问题不嫌麻烦完全可以用dp解决，而反之则不一定，就比如样例这道题，如果直接贪心为4+1+1三枚，dp的话就可以得出3+3两枚；怎么说呢，其实我感觉贪心和dp有种包含关系，也就是有些特殊的dp题可以用贪心做；至于什么时候能用贪心得到全局最优解……这个要根据题目自己证明判断啦吧……新人第一次答题，有什么不好的地方还请各位多多包涵指正；最后，再次谢邀 @plyjdz 这位大佬不屑于回答小问题，指派我这个小弟来卖萌。
■网友
谢邀。我咋记得看过类似的问题呢==鄙人不才，就按照我的理解胡说八道两句。两者的本质都是把一个具体问题分解为子问题，子问题再分解成子问题的子问题，最后一级子问题就是已有的条件，那么一个困难的问题就可以由简单的子问题通过状态转移得出答案。可以说贪心法是一种特殊的动态规划，区别就在于状态转移，动态规划的状态转移是由多个子问题转移的，而贪心法也是从一个子问题转移的。也就是说，如果把求解的过程画出来，动态规划是一颗树，而且贪心是剪枝成一条链。要问什么时候用哪个，就看你状态转移方程是从一个子问题还是从多个子问题进行转移。


推荐阅读


上一篇：魔兽世界的兽人语、鱼人语是怎样设计出来的

下一篇：Apple Music上线半年付费用户1000万，是否可超越Spotify