第13章贪心算法
贪心算法
局部最优求得总体最优
适用于桌上有6张纸币，面额为100 100 50 50 50 10，问怎么能拿走3张纸币，总面额最大？—拿单位价值最高的
- 只关注局部最优----关注拿一张的最大值
- 拆解-----拿三次最大的纸币
不适用于桌面三件物品，每个物品都有重量和价值，
w v
6 9
5 7
3 3
承重为8，求不超过背包承重情况下最大价值
- 只能选一件，能不能得到最大值----选 6 9
- 还剩下二，能选第二件吗？不能选
所以不适用，因为不能局部最优求得总体最优
贪心算法的设计就是一次一次用偏序关系证明贪心策略
偏序关系
在数学中，偏序集合是有序理论中，指配备了部分排序关系的集合（集合没有顺序，但加了一个用于排序的关系），将排序，顺序或排列这个元素的直觉概念抽象化。
使用偏序关系的传递性：xRy,yRz–>xRz,局部最优使得全局最优
例题1-国王游戏
排在该大臣前面的所有人的左手上的数的乘积除以他自己右手上的数,然后向下取整得到的结果。
国王不希望某一个大臣获得特别多的奖赏，所以他想请你帮他重新安排一下队伍的顺序，使得获得奖赏最多的大臣，所获奖赏尽可能的少。注意，国王的位置始终在队伍的最前面。
输出一个整数，表示重新排列后的队伍中获奖赏最多的大臣所获得的金币数。
C[i]=A[j]/B[i] :累乘从0到i-1
微扰：调整i和i+1位置的大臣，观察序列前后的变化:
微调的两个元素A[i]和A[i+1]只会改变他们两本身：所以微调后的C[i]'和C[i+1]'同时小于C[i+!]
A[i]xB[i] >= A[i+1]xB[i+1] :越小越往前，越大越往后
#include <iostream>
#include <algorithm>
using namespace std;
#define MAX_N 1000
int a[MAX_N+5],b[MAX_N+5],ind[MAX_N+5]; //使用ind不对原数组排序，对下标数组排序
void acm_1_6_paixu_GuowangYouxi_test(){
// A[i]xB[i] >= A[i+1]xB[i+1] :越小越往前，越大越往后
int n;
cin >> n;
for(int i=0;i<=n;i++){
cin >>a[i]>>b[i]; //左右手
ind[i]=i;
}
sort(ind+1,ind+n+1,[&](int i,int j)->bool{
return a[i]*b[i]<a[j]*b[j];
});
//统计大臣获得的最多金币数量
int p=a[0],ans=0;
for (int i=1;i<=n;i++){
if(p/b[ind[i]]) //ind[i]表示排完序之后大臣的编号
ans=p/b[ind[i]];
p*=a[ind[i]];
}
cout << ans<<endl;
}
int main(){
acm_1_6_paixu_GuowangYouxi_test();
return 0;
}
def acm_1_6_paixu_GuowangYouxi_test():
n=int(input())
a=list(range(n+1))
b=list(range(n+1))
ind=list(range(n+1))
for i in range(n+1):
a[i],b[i]=list(map(int,input().split()))
ind[i]=i
ind[1:]=sorted(ind[1:],key=lambda i:a[i]*b[i]) #按照a[i]*b[i]从小到大排序
ans=0
p=a[0]
for i in range(1,n+1):
if(p//b[ind[i]]>ans):
ans=p//b[ind[i]]
p*=a[ind[i]] #左边所有大臣左手累乘
print(int(ans))
acm_1_6_paixu_GuowangYouxi_test()
最大整数
局部最优：a+b > b+a
arr.sort(key=cmp_to_key(cmp2))
from functools import cmp_to_key
def cmp2(a,b):
if a + b > b + a: #大于
return -1
elif a + b < b + a: #小于
return 1
else:
return 0 #相等
def test():
n=int(input())
arr = input().split()
arr.sort(key=cmp_to_key(cmp2))
print("".join(arr))
test()
#include <string.h>
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp(const string &a,const string &b){
return a+b > b+a;
}
int main(){
vector<string> arr;
string s;
int n;
cin >> n;
for (int i=0;i<n;i++){
cin >> s;
arr.push_back(s);
}
sort(arr.begin(),arr.end(),cmp);
for(int i=0;i<n;i++){
cout <<arr[i];
}
cout <<endl;
}
删除
每次删除一位，保证删除一位后得到的结果位删除一位最小值
#include <iostream>
using namespace std;
#define MAX_N 500
int main(){
char s[MAX_N+5];
int k;
cin >> s >>k;
for(int i=0;i<k;i++){ //进行k次删除，每次删除一位
int j=0;
//留下n-1位的最小值
while(s[j+1] !='\0' && s[j] <= s[j+1]){
++j;
}
//12343 //得到第一个逆序位高位4
while(s[j]) s[j]=s[j+1],j++; //后面的向前移动
//完成一轮删除
}
for(int i=0,flag=1;s[i];i++){
if(s[i]=='0' && flag){
//首位0不输出
//flag表示有没有输出过数字
continue;
}
cout << s[i];
flag=0;
}
cout <<endl;
return 0;
}
#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 Cry, Inc. All Rights Reserved
#
# @Time : 2024/4/10 11:47
# @Author : Cry
# @File : 删数、.py
# @IDE : PyCharm
s=input()
n=int(input())
for i in range(n):
for j in range(len(s)+1):
if j+1==len(s):
s=s[:j]+s[j+1:]
break
if s[j]>s[j+1]:
s=s[:j]+s[j+1:]
break
print(int(s))
HZOJ 503独木舟
每次找最重和最轻的坐在一起
能坐在一起就一起走
不能坐在一起，就只让重的坐一条船
//
// Created by cry on 2024/4/10.
//
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
void acm_1_13_tanxin_DumuZHou_test(){
int w,n;
cin >>w >> n;
vector<int> arr(n);
for(int i=0;i<n;i++){
cin >> arr[i];
}
sort(arr.begin(),arr.end());
int i=0,j=n-1,cnt=0; // i为最轻的 j为最重的
while(i<j){
//最轻的和最重的能不能坐一个船
if(arr[i]+arr[j]<=w){
i++,j--;
}else
j--;
cnt+=1;
}
if(i==j) cnt+=1; //还剩一个人
cout << cnt<<endl;
}
#!/usr/bin/python3
# _*_ coding: utf-8 _*_
#
# Copyright (C) 2024 - 2024 Cry, Inc. All Rights Reserved
#
# @Time : 2024/4/10 12:22
# @Author : Cry
# @File : 独木舟.py
# @IDE : PyCharm
w=int(input())
n=int(input())
arr=list(range(n))
for i in range(n):
arr[i]=int(input())
arr=sorted(arr)
i=0
j=n-1
cnt=0
while(i<j):
if(arr[i]+arr[j]<=w):
i+=1
j-=1
else:
j-=1
cnt+=1
if(i==j):
cnt+=1
print(cnt)