[IMUDGES内部培训]贪心

发布于 2018-11-09  16 次阅读


硬币问题

IMUDGES 1193

#include <iostream>
using namespace std;
int main()
{
    int n,a;
    int money[]={100,50,10,5,2,1};
    while (cin>>n&&n)
    {
        int ans=0;
        for (int i = 0; i < n; ++i) {
            cin>>a;
            for (int j = 0; j < 6; ++j) {
                ans+=a/money[j];
                a%=money[j];
            }
        }
        cout<<ans<<endl;
    }
}

练习: 有n个物体,第i个物体的重量为wi(wi为正整数)。选择尽量多的物体,使得总重量不超过C。

注意:有些硬币问题需要使用动规 IMUDGES 1558

如果采用之前的策略,此数据就过不了

6 100
2 5 8 9 11 30

#include <iostream>
#include <algorithm>
#include <cmath>

using namespace std;
int value[1005], n, cost;
int dp[10000 + 5];
const int INF=0x3f;
int main() {
    while (cin >> n >> cost) {
        for (int i = 0; i < n; ++i) {
            cin >> value[i];
        }
        dp[0] = 0;
        for (int i = 1; i <= cost; ++i) {
            dp[i] = INF;
            for (int j = 0; j < n; ++j) {
                if (i - value[j] >= 0)dp[i] = min(dp[i], dp[i - value[j]] + 1);
            }
        }
        if (dp[cost] == INF) {
            cout << "bad\n";
        } else {
            cout << dp[cost] << endl;
        }

    }
}

简介

贪心算法是指:在每一步求解的步骤中,它要求“贪婪”的选择最佳操作,并希望通过一系列的最优选择,能够产生一个问题的(全局的)最优解。

贪心算法每一步必须满足以下条件:

  •  可行的:即它必须满足问题的约束。
  •  局部最优:他是当前步骤中所有可行选择中最佳的局部选择。
  • 不可取消:即选择一旦做出,在算法的后面步骤就不可改变了。

过河问题

IMUDGES 1800

区间问题

有n项工作,每项工作分别在si开始,ti结束。对每项工作,你都可以选择参加或不参加,但选择了参加某项工作就必须至始至终参加全程参与,即参与工作的时间段不能有重叠(即使开始的时间和结束的时间重叠都不行)。

限制条件:1<=n<=100000 1<=si<=ti,=10^9样例:输入n=5 s={1,2,4,6,8} T={3,5,7,9,10} 输出3

可知,每次选择结束时间最早的工作是最优的策略
pair<int,int> 结束时间放在first,开始时间放在second,便于排序也可以用有两个元素的结构体和一个比较函数来实现排序

POJ 1328可以转换成区间问题.保证每个区间里都有一个点(安装雷达);跟上题思路类似,将右端点进行排序

修栅栏/合并果子

POJ 3253
洛谷1090

每次选取最小的两个元素合并,选取最小元素可以用优先队列(stl,注意定义)

其余问题

prime,dijkstra,kruskal...

练习

IMUDGES 1272从两边往中间扫描

洛谷1223最短优先