, dp[i - coin] + 1)。
效果：dp[n]即为组成n分所需的最少硬币数目。
源代码：
void Knapsack(int n, float M, float v[], float w[], float x[]) {
Sort(n, v, w)
int i;
for (i = 1, i <= n; i++)
x = 0;
float c = M;
for (i = 1; i <= n; i++) {
if (w > c)
break;
x = 1;
c -= w;
}
if (i <= n)
x = c / w;
}
1.测试代码：
#include <iostream>
#include <vector>
#include <algorithm>
// 定义一个使命的结构体
struct Task {
int deadline; // 截止时间
int penalty; // 误时处罚
// 排序时使用的比较函数
bool operator<(const Task& other) const {
if (this->penalty != other.penalty) {
return this->penalty > other.penalty; // 先按误时处罚降序排序
}
return this->deadline < other.deadline; // 误时处罚相同时，按截止时间升序排序
}
};
// 贪心算法实现
std::pair<std::vector<int>, int> greedy_schedule(const std::vector<Task>& tasks) {
std::vector<Task> sorted_tasks = tasks;
std::sort(sorted_tasks.begin(), sorted_tasks.end()); // 对使命进行排序
int n = sorted_tasks.size();
std::vector<int> schedule(n, -1); // 初始化时间表为-1表示未安排
int total_penalty = 0; // 初始化总误时处罚为0
int current_time = 0; // 当前时间
for (int i = 0; i < n; ++i) {
if (current_time < sorted_tasks.deadline) { // 如果当前时间早于截止时间
schedule = current_time; // 安排使命
++current_time; // 更新当前时间
}
else {
total_penalty += sorted_tasks.penalty; // 错过截止时间，累加误时处罚
}
}
return { schedule, total_penalty };
}
// 测试代码
int main() {
std::vector<Task> tasks = { {3, 10}, {1, 5}, {2, 2}, {4, 7} }; // 使命列表
auto result = greedy_schedule(tasks);
std::vector<int> schedule = result.first;
int total_penalty = result.second;
std::cout << "时间表: ";
for (int time : schedule) {
std::cout << time << " ";
}
std::cout << std::endl;
std::cout << "总误时处罚: " << total_penalty << std::endl;
return 0;
}
运行效果：
时间复杂度分析阐明：
1.时间复杂度：
排序：使用标准库中的std::sort函数对使命列表进行排序。在最坏情况下，排序算法的时间复杂度是O(n log n)，此中n是使命的数目。
安排使命：这个步骤遍历排序后的使命列表一次，为每个使命安排时间或计算误时处罚。因此，这部门的时间复杂度是O(n)。
由于排序步骤的时间复杂度支配了整体时间复杂度，以是整个算法的时间复杂度是O(n log n)。
2.空间复杂度：
使命列表：算法必要一个额外的列表来存储输入的使命（如果输入不是直接以列表形式给出的）。这个列表的空间复杂度是O(n)，此中n是使命的数目。
时间表：算法创建了一个与使命列表大小相同的时间表，用于存储每个使命的安排时间。这个列表的空间复杂度也是O(n)。
排序：std::sort函数在排序过程中大概必要额外的空间（尽管它通常是原地排序，即不必要额外的空间，但在最坏情况下大概必要O(n)的额外空间）。
这个贪心算法的时间复杂度是O(n log n)，空间复杂度是O(n)。
2.测试代码：
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
int coinChange(std::vector<int>& coins, int amount) {
std::vector<int> dp(amount + 1, INT_MAX); // 初始化dp数组为最大值
dp[0] = 0; // 组成0分不必要硬币
// 遍历所有大概的金额
for (int i = 1; i <= amount; ++i) {
// 遍历所有硬币面值
for (int coin : coins) {
// 如果当前硬币面值小于等于当前金额i
if (coin <= i) {
// 更新dp，实利用用当前硬币
dp = std::min(dp, dp[i - coin] + 1);
}
}
}
// 如果dp[amount]的值仍然是初始的最大值，阐明无法组成amount分零钱
if (dp[amount] == INT_MAX) {
return -1; // 返回-1表示无法组成
}
else {
return dp[amount]; // 返回组成amount分所需的最少硬币数目
}
}
int main() {
std::vector<int> coins = { 25, 10, 5 ,1}; // 硬币面值
int amount = 14; // 目标金额
int result = coinChange(coins, amount);
std::cout << "组成" << amount << "分所需的最少硬币数目为：" << result << std::endl;
return 0;
}
运行效果：
14分：
29分：
32分：
时间复杂度分析阐明：
外层循环遍历从1到amount的每个金额i，以是它的时间复杂度是O(amount)。内层循环遍历硬币面值数组coins中的每个硬币面值coin，假设硬币面值的数目是n（即coins.size()），那么内层循环的时间复杂度是O(n)。因此，两层循环的总时间复杂度是外层循环和内层循环时间复杂度的乘积，即O(amount * n)。
10，7 ，1面额 14分：
19分：
98分：
面额：25，10，5，1
第一部门：25分，10分，5分，1分四种面额硬币
对于这个问题，我们可以使用贪心算法来求解，该算法会只管使用面额大的硬币来减少硬币的总数。以下是算法步骤：
1.如果n大于或等于25，则使用25分的硬币，并更新n = n - 25。
2.如果n小于25但大于或等于10，则使用10分的硬币，并更新n = n - 10。
3.如果n小于10但大于或等于5，则使用5分的硬币，并更新n = n - 5。
4.如果n小于5，则使用1分的硬币，并更新n = n - 1。
验证最优解
由于25, 10, 5, 1这四种面额硬币的选取满足贪心选择性子（即局部最优解能导致全局最优解），以是该贪心算法可以找到最优解。
面额：10，7，1
第二部门：10分，7分，1分三种面额硬币
对于这个问题，如果直接使用类似上述的贪心算法，大概无法找到最优解。
算法步骤如下：
1.如果n大于或等于10，则使用10分的硬币，并更新n = n - 10。
2.如果n小于10但大于或等于7，则使用7分的硬币，并更新n = n - 7。
3.如果n小于7，则使用1分的硬币，并更新n = n - 1。
但是，这种贪心计谋在某些情况下大概不是最优的。比方，当n = 14时，按照上述贪心计谋，会使用1个10分硬币和4个1分硬币，总共5个硬币。但是，使用2个7分硬币只必要2个硬币，这是一个更优的解。
缘故原由
对于10分，7分，1分这三种面额硬币，它们不满足贪心选择性子。即局部最优解（每次都选择当前可用的最大面额硬币）不一定会导致全局最优解。因此，对于这类问题，大概必要使用动态规划等其他算法来确保找到最优解。
六，实行总结与体会
经过本次实行，我深入了解了贪心算法在现实问题中的应用，特殊是在办理单元时间使命安排问题和最少硬币数找零钱问题中的有效性。
在单元时间使命安排问题中，我接纳了先按误时处罚降序排序，再按截止时间升序排序的贪心计谋。这种计谋确保了高误时处罚的使命优先被安排，而且只管在截止时间前完成。通过编程实现这一算法，我成功地找到了一个总误时处罚最小的使命时间表。这一过程中，我体会到了贪心算法在办理优化问题时的直观性和有效性。
在最少硬币数找零钱问题中，我起首使用了贪心算法来实行办理。对于25分、10分、5分和1分的硬币组合，贪心算法可以或许找到最优解。然而，当硬币组合变为10分、7分和1分时，我意识到贪心算法大概不再适用。这是因为某些情况下，贪心计谋选择的硬币组合并不是最优的。这一发现让我对贪心算法的适用性和范围性有了更深刻的明白。
通过这次实行，我深刻体会到了算法筹划的重要性。不同的算法适用于不同的问题，而选择合适的算法是办理问题的关键。贪心算法作为一种直观且有效的优化算法，在办理某些问题时可以或许取得很好的效果。但是，它也有其范围性，不能适用于所有问题。因此，在现实应用中，我们必要根据问题的特点选择合适的算法。
别的，实行也让我认识到了编程实践的重要性。通过编程实现算法，我可以或许更深入地明白算法的原理和实现过程。同时，编程实践也让我发现了本身在算法筹划和编程本领方面的不足，为我今后的学习和进步指明白方向。
最后，我想说的是，实行是一个不断学习和进步的过程。通过不断地实践和总结，我们可以或许不断进步本身的算法筹划和编程本领，为办理更复杂的问题打下坚固的底子。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
| 欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/) |
Powered by Discuz! X3.4 |
