- 硬幣問題
- 區(qū)間問題
- 字典序
- 其他
- Saruman’s Army
- Fence Repair
我們可以通過做出局部最優(yōu)選擇來構(gòu)造全局最優(yōu)解捻浦，我們直接做出當(dāng)前問題中看來最優(yōu)的選擇晤揣，而不必考慮子問題的解。
貪心算法通常是自頂向下的昧识，進(jìn)行一次又一次選擇盗扒，將給定問題實例變得更小跪楞。
2.2.1 硬幣問題
從￥500~￥1每次選擇盡可能多的硬幣個數(shù)侣灶。
<pre><code>
//
// Created by Nathan on 15/3/22.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// V: 2 0 3 1 2 3
// A: 620
//
include <iostream>
using namespace std;
int coin[6];
const int v[6]={1,5,10,50,100,500};
int A;
int solve(){
int res = 0;
int tmp = 0;
for (int i = 5;i>=0 ; i--) {
if(coin[i]&&(A-tmp)/v[i]){
int s = min((A-tmp)/v[i],coin[i]);
res += s;
tmp += s*v[i];
}
}
if(tmp==A) return res;
return 0;
}
int main(int argc, const char * argv[]) {
for (int i = 0; i<6; i++) {
cin >> coin[i];
}
cin >> A;
cout << solve() << endl;
return 0;
}
</code></pre>
2.2.2 區(qū)間問題
正確的算法：在可選的工作中习霹，每次都選擇最早結(jié)束的工作。
<pre><code>
//
// Created by Nathan on 15/3/22.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// 5
// 1 2 4 6 8
// 3 5 7 9 10
//
include <iostream>
using namespace std;
const int N =100000;
int n,s[N],t[N];
typedef pair<int, int>P;
pair<int,int>V[N];
int solve(){
for (int i = 0;i < n;i++) {
V[i].first = t[i];
V[i].second = s[i];
}
sort(V, V+n);
int res = 0,t=0;
for (int i = 0; i < n ;i++) {
if(t < V[i].second){
t = V[i].first;
res++;
}
}
return res;
}
int main( int argc, const char * argv[]) {
cin >> n;
for (int i = 0; i<n; i++) {
cin >> s[i];
}
for (int i = 0; i<n; i++) {
cin >> t[i];
}
int res = solve();
cout << res << endl;
return 0;
}
</code></pre>
2.2.3 字典序最小問題
什么是 字典序 淋叶？
<pre><code>
//
// Created by Nathan on 15/3/22.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// N = 6
// S : ACDBCB
//
include <iostream>
using namespace std;
const int N = 2000;
char S[N];
int n;
void solve(){
int a = 0 , b = n-1;
while (a<=b) {
bool left = false;
if(S[a] < S[b]){
left = true;
}
if (left) {
cout << S[a++];
} else {
cout << S[b--];
}
}
}
int main(int argc, const char * argv[]) {
cin >> n;
for (int i = 0; i < 6; i++) {
cin >> S[i];
}
solve();
return 0;
}
</code></pre>
2.2.4 其他
1. Saruman’s Army
思路：每次選擇范圍以外的最近一點作為下次遍歷的初始點。
<pre><code>
//
// Created by Nathan on 15/3/23.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// N = 6,R = 10
// X = 1,7,15,20,30,50
//
include <iostream>
using namespace std;
const int MAX_N = 1000;
int X[MAX_N],N,R;
int solve(){
sort(X, X+N);
int i=0 ,ans=0;
while (i < N) {
int s = X[i++];
while ( i < N && X[i] <= s+R) {
i++;
}
int p = X[i-1];
while (i < N && X[i] <= p+R) {
i++;
}
ans++;
}
return ans;
}
int main(int argc, const char * argv[]) {
cin >> N >> R;
for (int i = 0; i < N; i++) {
cin >> X[i];
}
int res = solve();
cout << res << endl;
return 0;
}
</code></pre>
2. Fence Repair
思路：尋找最小的兩個點处嫌，并從數(shù)據(jù)中刪除，將這兩個點的和放入數(shù)組中捆昏，繼續(xù)尋找最小的兩個點，直至剩余一個點為止遍烦。
<pre><code>
//
// Created by Nathan on 15/3/23.
// Copyright (c) 2015年 Nathan. All rights reserved.
//
// N = 3
// L : 8,5,8
//
include <iostream>
using namespace std;
const int MAX_N = 20000;
int n,L[MAX_N];
void solve(){
long long ans = 0;
while ( n > 1) {
int mii1 = 0,mii2=1;
if (L[mii1] > L[mii2]) {
swap(L[mii1], L[mii2]);
}
for (int i = 2; i < n; i++) {
if (L[i] < L[mii1]) {
mii2 = mii1;
mii1 = i;
} else if(L[i] < L[mii2]){
mii2 = i;
}
}
int t = L[mii1]+L[mii2];
ans +=t;
if(mii1==n-1){
swap(mii1, mii2);
}
L[mii1] = t;
L[mii2] = L[n-1];
n--;
}
cout << ans << endl;
}
int main(int argc, const char * argv[]) {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> L[i];
}
solve();
return 0;
}
</code></pre>
