算法设计与分析报告5 贪心算法

本文发布地址（方便阅读）：

  1. https://cmd.dayi.ink/WfnxTsYRQ4OdwI587BGDRQ
  2. https://blog.dayi.ink/?p=89
  3. https://www.cnblogs.com/rabbit-dayi/p/17817387.html
  4. https://type.dayiyi.top

1. 硬币找零问题

贪心

就是假设我们是收银员，需要找零，然后需要选取最少的硬币数量给他人。

我们直接从最大的依次给，给不了就给再小的，很爽。

但贪心的原理是子问题最优解推出整体问题最优解，也就是最优子结构，而对于子问题，只考虑当前怎么做最优，而不考虑整体情况，对于这个我们就只考虑现在需要的硬币而不考虑整体需要多少硬币。

实际的贪心问题需要证明，但是都贪心了，就贪心一点，不要那么多，直接做贪！

n = eval(input()) #要贪心的数额
arr = [10,5,1] # 面额
ans = 0
for i in arr:
  if n>=i:
    k = n//i #整除
    n -= i*k
    ans += k
    print(f"[info]{i} * {k}")

if ans ==0:
  print(-1)
else:print(ans)

  1. 最大面额的硬币比任何其他可能的硬币组合能表示的最大金额还要大。 这意味着任何较大金额的找零都应该首先尽可能多地使用最大面额的硬币
  2. 较小的硬币面额能被较大的硬币面额整除。
  3. 组合属性。 对于任意两个硬币面额a和b，如果a > b，那么对于任何金额x，如果x能够用a来找零，那么x - b也能用a来找零。移除一个较小面额的硬币并不会改变剩余金额能否用较大面额的硬币找零。也就是说，x可以被a整除或者x大于a，那么从x中减去b（得到的金额是x-b）仍然能够使用面额为a的硬币找零。

比如这道题：

https://www.luogu.com.cn/problem/B3635

如果我们需要15元，我们的贪心算法会这样找：

15
15 - 1*11
4 - 4*1

这样就需要5枚硬币，而这里，我们则只需要3枚硬币（3*5）。

一般这两种情况会导致：

  1. 硬币的面额不能互相组合出更小的面额中的任何一个。
  2. 较小面额的硬币不能组合成较大面额的硬币。

对于本题中的硬币系统，因为不能保证使用最大面额的硬币后，剩下的金额还能用较小的面额凑出，所以这里不能用贪心算法。

那咋办嘛？

动态规划（Oh no）

  1. 定义状态：

    • dp[i] 凑成总金额 i 所需的最少硬币数量。

      假设我们想要凑成金额为6元，那么 dp[6] 将包含以下集合：

      • {1, 1, 1, 1, 1, 1}：使用六个1元硬币 1个硬币
      • {1, 5}：使用一个1元和一个5元硬币 2个硬币

  2. 状态初始化：

    • dp[0] = 0，因为凑成总金额0不需要任何硬币。
    • 其他状态初值可以设为无限，表示还没有找到凑成这个金额的方法。

  3. 状态转移方程：

    • 要凑成总金额 i，可以通过以下三种方式：

      • 用一个1元硬币加上金额为 i-1 的最优解
      • 用一个5元硬币加上金额为 i-5 的最优解
      • 用一个11元硬币加上金额为 i-11 的最优解
    • 因此，状态转移方程为 dp[i] = min(dp[i-1], dp[i-5], dp[i-11]) + 1。

  4. 计算顺序：

    • 由小到大计算 dp[i]，计算到 dp[n]。

  5. 结果：

    • dp[n]
n = eval(input())
dp = [0x3f3f3f3f for i in range(n+1)]
dp[0]=0
for i in range(1,n+1):
  dp[i] = min(dp[i-1],dp[i-5],dp[i-11])+1
print(dp[n])

再来一道一样的题目题：

https://vjudge.net/problem/%E8%AE%A1%E8%92%9C%E5%AE%A2-T1781

n,m = map(int,input().split())
arr = list(map(int,input().split()))
dp = [0x3f3f3f3f for i in range(m+10)]
dp[0]=0
for i in range(1,m+1):
  for j in arr:
    if i>=j:
      dp[i] = min(dp[i-j]+1,dp[i])

if dp[m]==0x3f3f3f3f:
  print(-1)
else:
  print(dp[m])

..

AC:

2.活动安排问题

设有 n 个活动的集合 E={1,2,..,n}，其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi，且 si<fi。如果选择了活动 i ，则它在时间区间 [si,fi) 内占用资源。若区间[si,fi) 与区间 [sj,fj) 不相交，则称活动 i 与活动 j 是相容的。也就是说，当 fi≤sj 或 fj≤si 时，活动 i 与活动 j 相容。选择出由互相兼容的活动组成的最大集合。

这道题是纯贪心啦（DP也能做）：

总是选择结束时间最早的活动，这样留给其它活动的时间就最多了，选择后使得对其他活动影响最小。（证明就不证了）

  1. 将所有活动按照结束时间进行排序。
  2. 选择结束时间最早的活动。
  3. 剔除所有与已选择活动时间上有冲突的活动。
  4. 重复步骤 2 和 3，直到没有剩余的活动为止。
# 时间复杂度 O(nlogn)（排序）
n = eval(input())
ls = [ ]
for i in range(n):
  st,end = map(int,input().split())
  ls.append((st,end))
ls.sort(key=lambda x:x[1])
# [(1, 3), (2, 5), (4, 6), (1, 7)]
# print(ls)
# vis = [0 for i in range(ls[-1][1]+10)]
now = 0
ans = 1 # 选了排序后的第一个
for i,v in enumerate(ls):
  print(v)
  # 如果起始时间大于5等于现在的终止时间（注意集合开闭）
  if v[0]>=ls[now][1]:
    now = i
    ans+=1
print(ans)

3.背包问题

  • 因为完全背包和01背包都在之前的实验里有啦
  • 这里就拿这两种问题下的和课本样例输出下fi数组吧！

01 背包

n,c= 4,8
w = [0,2,4,5,3]
v = [0,5,4,6,2]
# 01背包
dp=[[0 for _ in range(c+10)]for i in range(n+10)]
for i in range(n+1):
  dp[i][0]=0

for i in range(1,n+1):
  for j in range(0,c+1):
    if j-w[i]<0:
      dp[i][j] = dp[i-1][j]
    else:
      dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i])

for i in range(0,n+1):
  for j in range(0,c+1):
    print(f"{dp[i][j]}",end=" ")
  print()
0 0 0 0 0 0 0 0 0 
0 0 5 5 5 5 5 5 5 
0 0 5 5 5 5 9 9 9 
0 0 5 5 5 6 9 11 11 
0 0 5 5 5 7 9 11 11

回溯选择了什么：

# 回溯找出选中的物品
selected = []
i, j = n,c
while i>0 and j > 0:
  if dp[i][j] != dp[i-1][j]:
    selected.append(i)
    j -= w[i]
  i -= 1
selected.reverse()  # 因为是逆向查找的
for item in selected:
    print(f"Sel:{item} weight:{w[item]} value:{v[item]}")

贪心？

我觉得是不对的啦

至少不一定可以求出最优解，贪心算法在每一步都选取当前最优的选择，但是对于01背包问题，当前最优的选择不一定能导致全局最优解。

就比如这样，假设背包的容量为10，有以下三件物品：

  • 物品A：重量3，价值5
  • 物品B：重量4，价值6
  • 物品C：重量7，价值10

如果使用贪心算法根据单位重量价值（价值除以重量）来选择物品，我们将会选择物品A（单位重量价值为1.67）和物品B（单位重量价值为1.5），总重量为7，总价值为11。
但是，最优解是选择物品B和物品C，总重量为11（如果背包可以装11的话），总价值为16。

但是课本例题的数据如果用这种贪心似乎还能跟DP选的一样，但这不能全部情况啦

n,c= 4,8

w = [0,2,4,5,3]
v = [0,5,4,6,2]
# 贪心

v_old = -1.00
ans_val = 0
left_c =  c
for i in range(1,n+1):
  v_now = v[i]/w[i]
  if v_now>v_old and left_c>=w[i]:
    ans_val+=v[i]
    left_c-=w[i]
    print(f"Sel:{i} weight:{w[i]} value:{v[i]} attempt:{v_now}")
  v_old = v_now

print(ans_val)

输出结果，虽然跟01 DP一样，但是这个题目正确不能说明对于全部正确。

Sel:1 weight:2 value:5 attempt:2.5
Sel:3 weight:5 value:6 attempt:1.2
11

比如这样一组数据就没法正常贪心成功：

所以贪心不能代表全部，也经常不能得出正确解（不如说得出正确解是巧合）

完全背包

假设背包容量还是这个情况（C=8），但是我们的物品有无限个。

这里数据比较小，没有用递推优化DP

# 完全背包
dp=[[0 for _ in range(c+10)]for i in range(n+10)]
for i in range(n+1):
  dp[i][0]=0

for i in range(1,n+1):
  for j in range(0,c+1):
    for k in range(0,int(j/w[i])+1,1):
      dp[i][j] = max(dp[i-1][j-k*w[i]]+v[i]*k,dp[i][j])

for i in range(0,n+1):
  for j in range(0,c+1):
    print(f"{dp[i][j]}",end=" ")
  print()

0 0 0 0 0 0 0 0 0 
0 0 5 5 10 10 15 15 20 
0 0 5 5 10 10 15 15 20 
0 0 5 5 10 10 15 15 20 
0 0 5 5 10 10 15 15 20
最后修改：2023 年 11 月 08 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏