贪心c++介绍
前言
有1元，5元10，元，20元，100元，200，元的钞票无穷多张。先使用这些钞票支付x元支付x元，最少需要多少张？
列如,X= 628
最佳支付方法
3张200的，一张20的，1张5块的，3张一块的，共需要8张
直觉告诉我们：尽可能的多实用面值较大的钞票
贪心：遵循某种规律，不断贪心的选取当前最优策略的算法设计方法
为什么这么做是对的，面额为1元，5元，10元，20元，100元，200元，任意面额是比自己小的面额的倍数关系。
所以当使用一张较大面额的钞票时，若用较小面额钞票替换，，一定需要更多的其他面额钞票。
如10 = 5 + 5
故当前最优解即为全局最优解，贪心成立
思考：如果增加7元面额，贪心还成立吗？（不成立，不满足倍数关系，可以用动态规划解决）
代码：
#include <iostream>
using namespace std;
int main()
{
int rmb[] = {200,100,20,10,5,1};
int num = 6; //六种面值
int x = 628;
int count = 0;
for(int i =0 ;i < num;i++)
{
int use = x/rmb[i];
count += use;
x = x - rmb[i] * use;
printf("需要支付面额为%d的%d张，",rmb[i],use);
printf("剩余需要支付金额%d.\n", x);
}
printf("总共需要支付%d张\n",count++);
}
下面用六个题目深入了解贪心
LeetCode455分发饼干
思考：
做这个题目考虑好俩个问题
第一： 当某个孩子可以被多个饼干满足时，是否需要优先用某个饼干满足这个孩子
第二：当某个饼干可以满足多个孩子时是否需要优先满足某个孩子
为了让更多孩子得到满足有如下规律
1：某个饼干不能满足某个孩子，则饼干也不一定满足需求因子更大的孩子；
2：某个孩子可以更小的饼干满足，没必要用更大的糖果满足，因此可以保留更大的饼干满足需求因子更大的孩子（贪心）
3：孩子的需求因子更小更容易满足，姑优先从需求因子小的孩子尝试，可以得到正确的结果
算法思路：
1、将g与s从小到大排序
2、从小到大的顺序使用各个饼干尝试是否可以满足某个孩子，每个饼干只尝试1次，若尝试成功，则换一个孩子尝试，知道发现没更多孩子或者没更多的的饼干，循环结束
代码：
class Solution {
public:
int findContentChildren(vector<int>& g, vector<int>& s) {
sort(g.begin(),g.end());
sort(s.begin(),s.end());
int child = 0; //代表满足几个孩子
int bis = 0; //代表尝试几个饼干
while(child < g.size() && bis <s.size()){
if(g[child] <= s[bis]){
child++; //满足孩子孩子指针向后移动
}
bis ++; //每个饼干只尝试一次
}
return child;
}
};LeetCode376摆动序列
思考：
[1,17,5,10,13,15,10,5,16,8],整体不是摇摆序列，观察该序列前六位：[1,17,5,10,13,15]橙色部分为上升段：
其中它的三个子序列是摇摆序列：
[1,17,5,10...]
[1,17,5,13...]
[1,17,5,15...]
在不清楚原始第七位是什么情况下，只看前六位，摇摆子序列的第四位从10,13,15中选择一个数
思考选则那个好
我们的目的是希望第七位成为摇摆序列的概率更大，，应该尽可能的选择大的更大的，所以选择15
思路
状态机
代码
class Solution {
public:
int wiggleMaxLength(vector<int>& nums) {
if (nums.size() < 2){
return nums.size();
}
static const int BEGIN = 0;
static const int UP = 1;
static const int DOWN = 2;
int STATE = BEGIN;
int max_length = 1;
for(int i = 1;i < nums.size();i ++){
switch(STATE){
case BEGIN:
if(nums[i-1] < nums[i]){
STATE =UP;
max_length ++;
}
else if(nums[i-1] > nums[i]){
STATE = DOWN;
max_length++;
}
break;
case UP:
if(nums[i-1]>nums[i]){
STATE =DOWN;
max_length++;
}
break;
case DOWN:
if(nums[i-1] < nums[i]){
STATE =UP;
max_length++;
}
break;
}
}
return max_length++;
}
};
- 点赞
- 收藏
- 关注作者
评论（0）