请给我代码:给定 nn 种货币,每种货币数量无限。 现在要求以最少的货币数目表示一个数 SS。 一种方法当然是 DP 求一个最优解了, 当然正常人的做法是贪心:每次取最大的不超过当前待表示数的货币。 现在,你的任务是证明正常人的表示法不一定最优:找到最小的 SS,使得正常人的表示法比理论最优解差,或说明这样的 SS 不存在
时间: 2023-02-10 20:51:42 浏览: 71
这是证明贪心策略的正确性的典型问题。
证明的思路是:假设存在一个数字 S,使得贪心策略无法得到最优解,并且有一组数字的选择方案使得贪心策略的结果比理论最优解差。
然后,我们可以通过反证法来证明这样的 S 不存在。
具体来说,我们可以考虑将 S 分解成若干个较小的数字,分别使用贪心策略和理论最优策略来解决这些较小的数字。然后,我们可以发现,贪心策略在处理这些较小的数字时也是最优的。所以,在处理 S 时,贪心策略仍然是最优的,这就与我们的假设矛盾。因此,证毕。
以下是用 Python 代码实现贪心策略的示例:
```
def greedy_strategy(S, denominations):
# 使用贪心策略表示数字 S
result = []
for coin in denominations:
while coin <= S:
S -= coin
result.append(coin)
return result
```
其中,`S` 表示要表示的数字,`denominations` 是货币的面额列表(按从大到小排列)。
相关问题
写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。
好的,这是一个常见的硬币找零问题,可以使用动态规划来解决。
具体来说,假设有一个货币系统,其中每种硬币的面值为 coins=[c1,c2,...,cn],我们要构造的面值为 amount,那么我们可以定义一个长度为 amount+1 的数组 dp,其中 dp[i] 表示构成面值 i 的方法数。
初始时,dp[0]=1,因为构成面值为 0 的方法只有一种,即不选任何硬币。对于每个硬币面值 ci,我们遍历数组 dp,如果 i≥ci,那么就可以使用面值为 ci 的硬币来构成面值 i,此时方案数为 dp[i-ci],因此我们可以得到状态转移方程:
dp[i] = dp[i] + dp[i-ci]
最终的答案即为 dp[amount]。
下面是完整的 Python 代码实现:
```python
def coinChange(coins, amount):
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
```
注意,这个算法的时间复杂度为 O(nm),其中 n 是硬币面值的个数,m 是要构造的面值。在实际应用中,当 m 很大时,这个算法可能会超时。
用C语言写一个程序来计算有多少种方法用给定的货币系统来构造一定数量的面值。
好的,下面是用 C 语言实现硬币找零问题的代码:
```c
#include <stdio.h>
int coinChange(int coins[], int n, int amount) {
int dp[amount + 1];
memset(dp, 0, sizeof(dp));
dp[0] = 1;
for (int i = 0; i < n; i++) {
for (int j = coins[i]; j <= amount; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
int main() {
int coins[] = {1, 2, 5};
int n = sizeof(coins) / sizeof(coins[0]);
int amount = 11;
int res = coinChange(coins, n, amount);
printf("%d\n", res);
return 0;
}
```
上述代码中,我们定义了一个长度为 amount+1 的数组 dp,初始化为全 0。然后,我们遍历硬币面值数组 coins,对于每个面值 ci,我们再遍历数组 dp,如果 i≥ci,那么就可以使用面值为 ci 的硬币来构成面值 i,此时方案数为 dp[i-ci],因此我们可以得到状态转移方程:
dp[i] = dp[i] + dp[i-ci]
最终的答案即为 dp[amount]。
值得注意的是,这个算法的时间复杂度为 O(nm),其中 n 是硬币面值的个数,m 是要构造的面值。在实际应用中,当 m 很大时,这个算法可能会超时。
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)