本关任务：设计一个贪婪算法，使得找的钱币张数最少。 商店售货员找给 1 个顾客 n 元，用以下七种面值的纸币：100 元，50 元，20 元，10 元，5 元，2 元，1 元。 思考：如果商店售货员找给 1 个顾客 140 元，假设钱币的面值有九种：100 元，70 元，50 元，20 元，10 元，7 元，5 元，2 元，1 元。用贪婪算法得到的是该问题的最优解吗？

### 回答1：
根据贪婪算法的思想，每次选择面值最大的纸币来找钱，可以使得找的钱币张数最少。但是对于这个问题，用贪婪算法得到的不一定是最优解。比如，如果商店售货员找给顾客 140 元，用九种面值的纸币，贪婪算法会先选择 100 元的纸币，然后再选择 20 元的纸币和两个 10 元的纸币，总共需要找出 4 张纸币。但是，更优的解法是选择 70 元的纸币和两个 35 元的纸币，总共只需要找出 3 张纸币。因此，贪婪算法得到的不是该问题的最优解。

### 回答2：
在这个问题中，我们需要找到一种方法来找零，使得用的钞票张数最小。这个问题可以通过贪婪算法来解决。

贪婪算法是一种常见的近似算法，它的基本思想是每次都选择局部最优解，并将其加入到最终解中。对于这个问题，我们可以从面值较高的纸币开始找零。

如果商店售货员需要找给顾客140元，我们可以考虑从100元开始，不断减去相应的面额，直到找完为止。这样我们可以得到1张100元和2张20元，总共使用了3张纸币。但是，如果纸币的面值是100元，70元，50元，20元，10元，7元，5元，2元，1元的九种，贪婪算法得到的就不是最优解。

如果按照贪婪算法的思路，我们首先从100元面值的纸币开始，但是100元无法满足需求，所以我们选择70元的纸币。接下来我们选择两张20元的纸币，然后选择一张10元的纸币，最后还剩下一元钱，我们直接使用1元纸币找零。这样我们使用了5张纸币。

然而，最优解应该是使用1张100元纸币和2张20元纸币，使用的总共钞票张数为3。可见，贪婪算法并不是一种一定能得到最优解的方法。

综上所述，贪婪算法在寻找零钱方面并不一定能得到最优解，因此在实际应用中需要根据具体情况选择合适的算法来解决问题。

### 回答3：
在计算机科学中，贪婪算法是一种解决优化问题的算法，它通过在每个局部做出最优决策来寻求全局最优解。对于商店售货员找钱的问题，贪婪算法是一种简单而有效的方法。

首先，我们需要将钞票按从大到小的顺序排列，这样我们可以确保在找钱时始终使用最大面值的纸币。然后，我们通过以下步骤找到最少的钞票张数：

1. 计算当前剩余需要找的钱数。
2. 在钞票列表中找到面值小于等于当前剩余钱数的最大面额纸币。
3. 如果找到了这样的钞票，将其加入钞票组合中并从剩余钱数中减去该面额钞票的价值。
4. 如果没有找到符合条件的钞票，则回到第二步。

例如，如果商店售货员需要找给顾客140元，我们可以采取以下步骤：

1. 剩余需要找的钞票数为140元。
2. 最大面值钞票为100元，将其加入钞票组合中并将剩余需要找的钞票数减去100元，变为40元。
3. 最大面值钞票为20元，将其加入钞票组合中并将剩余需要找的钞票数减去20元，变为20元。
4. 最大面值钞票为20元，将其加入钞票组合中并将剩余需要找的钞票数减去20元，变为0元。

因此，需要找的钞票张数为3张100元、1张20元，共计4张纸币。

回答该问题:
对于这个问题，贪婪算法并不能得到最优解。因为贪婪算法只关注每步局部最优解，而没有考虑整体最优解。在这个情况中，如果我们采用贪婪算法，它会先选择100元的面值纸币来找钱，然后只能选择50元和20元的面值纸币。这将会导致找钱的纸币张数为2张100元，2张20元，共计4张纸币。但是，更优的解决方案是采用2张70元的面值纸币和1张总值为5元的面值纸币，这样就只需要3张纸币。

综上所述，虽然贪婪算法在某些情况下可以解决问题，但不能保证它得到的解决方案一定是最优解。为了确保获得全局最优解，可能需要使用其他算法，比如动态规划。