概述:
? ? ? ?贪心算法是指，在对问题求解时，总是以当前情况为基础作最优选择，而不考虑各种可能的整体情况，它所做出的仅仅是在某种意义上的局部最优解，省去了为找最优解要穷尽所有可能而必须耗费的大量时间，类似数学归纳法，无后效性，在运行过程中没有回溯过程，每一步都是当前的最佳选择。
? ? ? ? 难点是如何贪心和证明贪心的正确性，即如何用一个小规模的解构造更大规模的解，比赛过程中需要胆大心细地归纳、分析。
贪心的缺点：
- 可能得不到最优解
- 可能算不出答案
用贪心法求解需要满足以下特征：
- 最优子结构性质（当一个问题的最优解包含其子问题的最优解时，称此问题具有最优子结构性质）
- 贪心选择性质
贪心常见问题
- 活动安排问题（区间调度问题）
- 区间覆盖问题
- 最优装载问题
- 多机调度问题
问题一
"Yakexi, this is the best age!" Dong MW works hard and get high pay, he has many 1 Jiao and 5 Jiao banknotes(纸币), some day he went to a bank and changes part of his money into 1 Yuan, 5 Yuan, 10 Yuan.(1 Yuan = 10 Jiao)
"Thanks to the best age, I can buy many things!" Now Dong MW has a book to buy, it costs P Jiao. He wonders how many banknotes at least,and how many banknotes at most he can use to buy this nice book. Dong MW is a bit strange, he doesn't like to get the change, that is, he will give the bookseller exactly P Jiao.
Input
T(T<=100) in the first line, indicating the case number.
T lines with 6 integers each:
P a1 a5 a10 a50 a100
ai means number of i-Jiao banknotes.
All integers are smaller than 1000000.
Output
Two integers A,B for each case, A is the fewest number of banknotes to buy the book exactly, and B is the largest number to buy exactly.If Dong MW can't buy the book with no change, output "-1 -1".
Sample Input
3
33 6 6 6 6 6
10 10 10 10 10 10
11 0 1 20 20 20
Sample Output
6 9
1 10
-1 -1
大致题意：?给定总钱数，一元，五元，十元，五十元，一百元的硬币的个数，求出使用最少和最多的硬币数。
思路：这是一个经典的贪心硬币问题，只需从大面值硬币开始选择，一直到最小面值的硬币，最后统计硬币的总数量，即为硬币的最少使用量。
硬币的最大使用量的求法则有些特殊，先求出总钱数与所有硬币总值的差值，再求出这部分差值使用硬币的最少数量，最后用总硬币数量减去差值使用硬币的最少数量，所得结果即为硬币的最多使用量。
代码:
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
int main() {
int t;
cin>>t;
while(t--) {
int mony,mony1=0;
int a,b,c,d,e;
int num=0;
int num1=0;
cin>>mony>>a>>b>>c>>d>>e;
mony1=a*1+b*5+c*10+d*50+e*100-mony;
int q=0;
//最少
if(mony>=100) {
q=mony/100;
if(q>=e) {
q=e;
}
mony-=100*q;
num+=q;
}
if(mony>=50) {
q=mony/50;
if(q>=d) {
q=d;
}
mony-=50*q;
num+=q;
}
if(mony>=10) {
q=mony/10;
if(q>=c) {
q=c;
}
mony-=10*q;
num+=q;
}
if(mony>=5) {
q=mony/5;
if(q>=b) {
q=b;
}
mony-=5*q;
num+=q;
}
if(mony>=1) {
q=mony/1;
if(q>=a) {
q=a;
}
mony-=1*q;
num+=q;
}
if(mony==0) {
cout<<num<<" ";
} else {
cout<<-1<<" ";
}
//最大
if(mony1>=100) {
q=mony1/100;
if(q>=e) {
q=e;
}
mony1-=100*q;
num1+=q;
}
if(mony1>=50) {
q=mony1/50;
if(q>=d) {
q=d;
}
mony1-=50*q;
num1+=q;
}
if(mony1>=10) {
q=mony1/10;
if(q>=c) {
q=c;
}
mony1-=10*q;
num1+=q;
}
if(mony1>=5) {
q=mony1/5;
if(q>=b) {
q=b;
}
mony1-=5*q;
num1+=q;
}
if(mony1>=1) {
q=mony1/1;
if(q>=a) {
q=a;
}
mony1-=1*q;
num1+=q;
}
if(mony1==0) {
cout<<a+b+c+d+e-num1;
} else {
cout<<-1;
}
cout<<endl;
}
return 0;
}
问题二
电子科大本部食堂的饭卡有一种很诡异的设计，即在购买之前判断余额。如果购买一个商品之前，卡上的剩余金额大于或等于5元，就一定可以购买成功（即使购买后卡上余额为负），否则无法购买（即使金额足够）。所以大家都希望尽量使卡上的余额最少。
某天，食堂中有n种菜出售，每种菜可购买一次。已知每种菜的价格以及卡上的余额，问最少可使卡上的余额为多少。
Input
多组数据。对于每组数据：
第一行为正整数n，表示菜的数量。n<=1000。
第二行包括n个正整数，表示每种菜的价格。价格不超过50。
第三行包括一个正整数m，表示卡上的余额。m<=1000。
n=0表示数据结束。
Output
对于每组输入,输出一行,包含一个整数，表示卡上可能的最小余额。
Sample Input
1
50
5
10
1 2 3 2 1 1 2 3 2 1
50
0
Sample Output
-45
32
?思路：突破口：将菜的价格从小到大排序，对前n-1个物品进行DP，找出消费金额不超过m-5的方案中最大的消费金额sum，在此基础上，m - (sum+price[n]) 即为卡内最小余额。因此，我们DP应在余额为0~m-5之内找出最优的解。
这道题中需要用到DP，即动态规划，详细讲解参考b站《动态规划 硬币问题》
动态规划 硬币问题_哔哩哔哩_bilibili
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<string.h>
#include<algorithm>
using namespace std;
int num[1005];
int dp[1005];
int main() {
int n;
while(cin>>n) {
if(n==0) {
break;
}
for(int i=0; i<n; i++) {
cin>>num[i];
}
memset(dp,0,sizeof(dp));
sort(num+0,num+n);
int mony;
cin>>mony;
if(mony<5) {
cout<<mony<<endl;
}else{
for(int i=0;i<n-1;i++){
for(int j=mony-5;j>=num[i];j--){
//dp[j]=max(dp[j],dp[j-num[i]]+num[i]);
if(dp[j]<dp[j-num[i]]+num[i]){
dp[j]=dp[j-num[i]]+num[i];
}else{
dp[j]=dp[j];
}
}
}
cout<<mony-dp[mony-5]-num[n-1]<<endl;
}
}
return 0;
}
|