一道题
舍友拿来了一道看起来像脑筋急转弯的算法题：
输入：
测试数据组数，过桥人数和每个人单独过桥时间
输出：
所需最少时间
题目后面给了一组测试数据
输入：
1
4
1，2，5，10
输出：
17
17是怎么来的，怎么这么少啊。
定式思维一直想着用1送所有人，但这要19阿。
舍友又发来了程序
一看，没有指针，学C学的半吊子的我还能看的懂，那就看看吧。
先输入数据
while 循环
似乎重点就在sum取min 的那一行
- sum后半部分思路：
就是我的思路，用最小的分别去送其他的每一个。 - 那前半部分是什么？
仔细一看，思路是这样： - 1和2先过桥
- 1回来送电筒
- 最大的两个过桥
- 2回来送电筒
- 若剩下人数大于3的话， 1和2再过桥
以此循环
两种思路取最小值，两个最大的过桥为一块，循环直到剩下人数<=3，然后根据剩下人数分三中情况，最后输出最小时间。
程序用来求最优解，将多人问题分解为两人两人的分块，以此循环，这好像就是贪心算法的题。
贪心算法是什么？
贪心算法（又称贪婪算法）是指，在对问题求解时总是做出在当前看来是最好的选择。不从整体最优上加以考虑，仅是在某种意义上的局部最优解。
- 核心 根据题意选取一种量度标准
- 性质 一种改进了的分级处理方法
概念简介
用贪婪法设计算法的特点是一步一步地进行，常以当前情况为基础根据某个优化测度作最优选择，而不考虑各种可能的整体情况，它省去了为找最优解要穷尽所有可能而必须耗费的大量时间，它采用自顶向下，以迭代的方法做出相继的贪心选择，每做一次贪心选择就将所求问题简化为一个规模更小的子问题，通过每一步贪心选择，可得到问题的一个最优解。
虽然每一步上都要保证能获得局部最优解，但由此产生的全局解有时不一定是最优的，所以贪婪法不要回溯。
对于一个给定的问题，往往可能有好几种量度标准，但其中的大多数量度标准作贪婪处理所得到该量度意义下的最优解并不是问题的最优解，而是次优解。因此，选择能产生问题最优解的最优量度标准是使用贪婪算法的核心。
根据当前状态做出在当前看来是最好的选择，即局部最优解选择，然后再去解做出这个选择后产生的相应的子问题。每做一次贪婪选择就将所求问题简化为一个规模更小的子问题，最终可得到问题的一个整体最优解。
基本思路
⒈ 建立数学模型来描述问题。
⒉ 把求解的问题分成若干个子问题。
⒊ 对每一子问题求解，得到子问题的局部最优解。
⒋ 把子问题的解局部最优解合成原来解问题的一个解。
最后再来看几道题
从零开始学贪心算法
1.钱币找零问题
假设1元、2元、5元、10元、20元、50元、100元的纸币分别有c0, c1, c2, c3, c4, c5, c6张。现在要用这些钱来支付K元，至少要用多少张纸币？
#include<iostream>
#include<algorithm>
using namespace std;
const int N=7;
int Count[N]={3,0,2,1,0,3,5};
int Value[N]={1,2,5,10,20,50,100};
int solve(int money)
{
int num=0;
for(int i=N-1;i>=0;i--)
{
int c=min(money/Value[i],Count[i]);
money=money-c*Value[i];
num+=c;
}
if(money>0) num=-1;
return num;
}
int main()
{
int money;
cin>>money;
int res=solve(money);
if(res!=-1) cout<<res<<endl;
else cout<<"NO"<<endl;
}
2.小船过河问题
只有一艘船，能乘2人，船的运行速度为2人中较慢一人的速度，过去后还需一个人把船划回来，问把n个人运到对岸，最少需要多久。
#include<iostream>
#include<algorithm>
using namespace std;
int main()
{
int a[1000],t,n,sum;
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
sum=0;
for(int i=0;i<n;i++) scanf("%d",&a[i]);
while(n>3)
{
sum=min(sum+a[1]+a[0]+a[n-1]+a[1],sum+a[n-1]+a[0]+a[n-2]+a[0]);
n-=2;
}
if(n==3) sum+=a[0]+a[1]+a[2];
else if(n==2) sum+=a[1];
else sum+=a[0];
printf("%d\n",sum);
}
}
好了，高数课也快下课了。
高数讲的好慢呐，哈哈哈哈哈
网友评论