今日复习内容：做题

例题1：蓝桥课程抢购

问题描述：

为了能让更多的同学学到IT技术，蓝桥云课又开始了课程限时打折活动。

作为初学者的你，希望尽可能买到含金量总额更高的课程，当然其他同学也是这么想。

由于购买课程的同学实在太多，蓝桥云课服务器宽带供不应求，导致同学们购买课程需要等待一定时间。

比如现在有3门课程：

《Java程序设计》需要等待3分钟，打折活动在3分钟后结束，该课程含金量为6；

《python程序设计》需要等待2分钟，打折活动在2分钟后结束，该课程含金量为3；

《c程序设计》需要等待1分钟，打折活动在3分钟后结束，该课程含金量为5。

方案一：选java，那么你可以抢购到含金量为6的课程。

方案二：可以先购买python，等待结束后再购买c，这样含金量就是8；

请注意，只能同时参与一门课程的抢购活动，且开始等待后不允许中途退出只有在打折活动有效期内才可以抢购课程。

输入格式：

第一行是一个整数N，代表蓝桥云课中有N门课程。

紧接着N行，每行3个正整数，A（购课等待时间），B（打折活动截止时间），C（课程含金量）。

输出格式：

输出一行一个整数，代表你能购买到课程最大的含金量总值。

参考答案：

def work():
    n = int(input())
    a = [[0,0,0]] + [list(map(int,input().split())) for i in range(n)]
    a.sort(key = lambda x:x[1])
    f = [[0]*(int(1e5) + 10)for i in range(n + 1)]
    for i in range(1,n + 1):
        for j in range(int(1e5) + 10):
            f[i][j] = f[i - 1][j]
            if a[i][1] >= j >= a[i][0]:
                f[i][j] = max(f[i][j],f[i - 1][j - a[i][0]] + a[i][2])
    print(max(f[n]))
if __name__ == '__main__':
    work()

运行结果：

 

以下是对此题的理解：

这道题是一个经典的动态规划问题，需要在有限的时间内选择购买课程以获取最大的含金量。

主要思路如下：

首先，从 输入中获取课程的数量n和没门课程的等待时间，结束时间和含金量。

对所有课程按照结束时间进行排序，这样可以方便后续的状态转移。

创建一个二维数组f，其中f[i][j]表示在前i门课程中，花费了j分钟等待时间所能获取的 最大含金量。

初始化f数组，将所有值设为0.

遍历每门课程，对于第i门课程：

遍历所有的等待时间j，如果当前课程的等待时间在[j,当前等待时间]的范围内，则更新f[i][j]为钱i - 1门课程中等待时间为j - 当前课程等待时间时的最大含金量加上当前课程的含金量。

最后，返回f[n][等待时间上限]中的最大值，即为最优解。

---

例题2：小兰的神秘礼物

问题描述：

小兰要过生日了，好朋友妮妮想送她一个礼物。妮妮找来了一个神秘的箱子，箱子的容量为v，她还收集了n个神秘的小物件，每个物件都有一个体积x。

妮妮想把这些物件中的一部分装进箱子里，当然也可以一个都不装。但是，为了增加神秘感，她希望箱子装得尽可能满，剩余的空间最小。你能帮妮妮计划一下，让她知道箱子最终的最小剩余空间吗？

输入格式：

第一行共一个整数V，表示箱子的容量。

第二行包含一个整数n，表示小物件的数量。

接下来n行，每行包含一个正整数x，表示第i个小物件的体积。

数据范围保证：0 < n <= 1000,1 <= x,v <= 1000

输出格式：

输出一个整数，表示箱子的最小剩余空间。

参考答案：

import os
import sys
v = int(input())
n = int(input())
f = [[0]*(v + 1) for i in range(n + 1 )]
for i in range(1,n + 1):
    vv = int(input())
    for j in range(v + 1):
        f[i][j] = f[i - 1][j]
        if j >= vv:
            f[i][j] = max(f[i][j],f[i - 1][j - vv] + vv)
print(v - f[n][v])

运行结果：

 

以下是我对此题的理解：

这道题目是一个经典的背包问题，需要在给定的箱子容量下，选择尽可能多的小物件装进箱子里，使得箱子装得尽可能满，剩余空间最小。

主要思路如下：

首先，从输入中获取箱子的容量和小物件的数量；

创建一个二维数组f，其中f[i][j]表示在前i个物件中，填满容量为j的箱子所剩余的最小空间；

初始化f数组，将其值全部设为0。

遍历每个小物件，对于第i个小物件：

遍历可能的箱子容量j，如果当前箱子容量j大于等于当前小物件的体积vv，则更新f[i][j]为前i - 1个物件中填满容量为j - 当前物件的体积vv的箱子所剩余的最小空间加上当前物件的体积vv；

最后，返回v与f[n][v]的差值，即为箱子所剩余的最小空间。

---

例题3：小蓝的神秘行囊

问题描述：

小蓝 是一名著名的探险家，他即将踏上异常特殊的寻宝冒险旅程。他的目标是寻找和收集各种神秘的宝物。他有一个神秘的行囊，能够装载各种物品。然而，这个行囊有一个特殊的规定：它的最大容量为v，并且它能承载的最大重量为m。

小蓝来到一个古老的城堡，里面有n件神秘的宝物，每件宝物只能被取走一次，每件宝物都有其特定的体积vi，重量mi和价值wi。

面对眼前的宝物，小蓝需要做出决定：将哪些宝物放入他的行囊，使得宝物的总体积不超过行囊的容量，总重量不超过行囊所能从承载的最大重量，且价值之和最大。

你的任务是帮助小蓝找出应该带走哪些宝物，并输出最大的宝物价值和。

输入格式：

第一行是3个整数n，v，m，分别用来表示宝物的数量，行囊的容量和能承载的最大重量。

接下来的n行，每行包括3个整数vi,mi,wi，分别表示每一个宝物的体积，重量和价值。

数据范围保证：0 < n <= 1000,0 < v,m <= 100,0 < vi,mi <= 100,0 < wi <= 1000

输出格式：

输出一个整数，表示可以装入行囊的宝物的最大价值。

参考答案：

n,v,m = map(int,input().split())
f = [[[0] * (m + 1)for i in range(v + 1)]for i in range(n + 1)]
for i in range(1,n + 1):
    vv,mm,ww = map(int,input().split())
    for j in range(v + 1):
        for k in range(m + 1):
            f[i][j][k] = f[i - 1][j][k]
            if j >= vv and k >= mm:
                f[i][j][k] = max(f[i][j][k],f[i - 1][j - vv][k - mm] + ww)
print(f[n][v][m])

运行结果：

---

例题4：加训啦

问题描述：

有一个兵营里面有n个士兵，每个士兵都有一个力量值ai。假设你是一名士兵长，你想通过训练，使得那么兵营的力量的下限尽可能大（兵营力量值的下限取决于兵营里面力量值最小的那个士兵）。

你有k点精力，m种训练计划，每种训练计划都有一个力量提升值bi，即一个士兵完成训练后，力量值会提升bi。

以及每种训练方法都有一个消耗值ci，即你每次分配训练计划你的精力都会消耗ci。

你可以消耗精力值分配训练方案给士兵，每种训练计划没有限制，即每个士兵可以训练任意训练计划 无数次，只要你的精力还够。

小蓝想让你告诉他，他的军营的兵营力量值的下限最大是多少？

输入格式：

输入共4行，第一行3个整数n，m，k，分别表示士兵数量，训练计划数和初始经历值。

第二行n个整数，表示每个士兵的初始力量值ai。

第3行m个正整数，表示每种训练计划的力量提升值 bi。

第4行m个正整数，表示每种训练计划的力量消耗值ci。

输出格式：

输出只有一行，表示兵营力量下限的最大值。

参考答案：

import math
def check(x):
    tot = 0
    for i in range(1,n + 1):
        if aa[i] < x:
            tot += f[m][x - aa[i]]
    return tot <= k
n,m,k = map(int,input().split())
aa = [0] + list(map(int,input().split()))
bb = [0] + list(map(int,input().split()))
cc = [0] + list(map(int,input().split()))
f = [[math.inf]*(int(1e4) + 100)for i in range(m + 1)]
f[0][0] = 0
for i in range(1,m + 1):
    for j in range(int(1e4) + 100):
        f[i][j] = min(f[i - 1][j],f[i][max(0,j - bb[i])] + cc[i])
left = 0
right = int(1e4) + 100
ans = -1

while left <= right:
    mid = (left + right) // 2
    if check(mid):
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

print(ans)

运行结果：

 

以下是我对此题的理解：

这道题目是一个经典的贪心算法问题，需要通过训练计划来提升士兵的力量值，使得兵营的力量下限尽可能大。
这段代码的主要思路如下：
1. 首先，从输入中获取士兵数量n，训练计划数m，以及初始经历值k。
2. 获取每个士兵的初始力量值ai，并记录每种训练计划的力量提升值bi和力量消耗值ci。
3. 创建一个函数check(x)，用于检查是否能够通过训练提升士兵的力量值至少为x。这个函数的实现逻辑是遍历每个士兵，如果其力量值小于x，则计算通过训练提升后的力量值是否能够达到x，如果达到则返回True，否则返回False。
4. 初始化二分查找的左右边界left和right，其中left初始化为0，right初始化为一个足够大的值（这里取了1e4 + 100）。
5. 使用二分查找的方式寻找力量下限的最大值。在每次迭代中，计算中间值mid，并调用check函数检查是否能够通过训练提升士兵的力量值至少为mid。如果能够达到，则更新ans为当前的mid，并将left更新为mid + 1；否则，将right更新为mid - 1。
6. 最终，输出ans即为兵营力量下限的最大值。
这样，代码利用贪心算法的思想，通过二分查找求解出兵营力量下限的最大值，从而达到优化士兵训练计划的目的。

我优化一下：

import math
def check(x):
    tot = 0
    for i in range(1,n + 1):
        if aa[i] < x:
            tot += f[x - aa[i]]
    return tot <= k
n,m,k = map(int,input().split())
aa = [0] + list(map(int,input().split()))
bb = [0] + list(map(int,input().split()))
cc = [0] + list(map(int,input().split()))
f = [math.inf]*(int(1e4) + 100)
f[0] = 0
for i in range(1,m + 1):
    for j in range(int(1e4) + 100):
        f[j] = min(f[j],f[max(0,j - bb[i])] + cc[i])
left = 0
right = int(1e4) + 100
ans = -1

while left <= right:
    mid = (left + right) // 2
    if check(mid):
        ans = mid
        left = mid + 1
    else:
        right = mid - 1

print(ans)

---

OK，今天就写到这里，下一篇继续！