说明：博主是大学生，有一门课是算法设计与分析，这是博主记录课程实验报告的内容，题目是老师给的，其他内容和代码均为原创，可以参考学习，转载和搬运需评论吱声并注明出处哦。
要求：3-1为算法分析题，写出主要的算法即可。3-2为算法实现题，要求写出：实验名称、实验过程描述（包括程序代码、测试用例、实验结果分析)、实验小结（包括实验过程中遇到的问题及体会）。
算法分析题3-1 二维0-1背包问题
给定n种物品和一背包。物品i的重量是wi ，体积是bi，其价值为vi，背包的容量为c，容积为d。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品时，对每种物品i只能有两种选择，即装入背包和不装入背包。不能将物品i装入背包多次，也不能只装入部分的物品i。尝试设计一个解决此问题的动态规划算法，并分析算法的时间复杂性。
主要算法思路：
设计一个三位数组dp，存放的值dp[i][j][k]代表前i个物品已经安排好，背包重量为j，体积为k时已经放入的物品的总价值。初始值dp[0][j][k]为0;对于每个物品，有两种选择，选和不选，首先判断是否能放下背包中，如果能，判断放入后，减去重量和体积，加上价值，是否比当前价值大，如果大的话加入，小的话不加入。
时间复杂性分析：
算法实现利用了三层循环，时间复杂性为O(n*c*d).
# a存放所有物品信息（二维列表a[价值][重量][体积]）,c背包容量,d容积,dp动态规划数组
def value_max(a, c, d):
n = len(a)
dp = [[[0 for _ in range(d + 1)] for _ in range(c + 1)] for _ in range(n + 1)]
for i in range(1, n+1): # 遍历每个物品
for j in range(c + 1): # 遍历所有可能的重量
for k in range(d + 1): # 遍历所有可能的体积
if j >= a[i-1][1] and k >= a[i-1][2]:
dp[i][j][k] = max(
dp[i - 1][j][k], # 不装入
dp[i - 1][j - a[i-1][1]][k - a[i-1][2]] + a[i-1][0] # 装入
)
else:
dp[i][j][k] = dp[i - 1][j][k]
return dp[n][c][d] # 最大价值
算法实现题3-2 独立任务最优调度问题
问题描述：
用2台处理机A和B处理n个作业。设第i个作业交给机器A处理时需要时间ai，若由机器B来处理，则需要时间bi。由于各作业的特点和机器的性能关系，很可能对于某些i，有ai>=bi，而对于某些j, j≠i，有aj<bj。既不能将一个作业分开由2台机器处理，也没有一台机器能同时处理2个作业。
设计一个动态规划算法，使得这2台机器处理完这n个作业的时间最短(从任何一台机器开工到最后一台机器停工的总时间)。
研究一个实例： (a1,a2,a3,a4,a5,a6)＝(2,5,7,10,5,2)；(b1,b2,b3,b4,b5,b6)＝(3,8,4,11,3,4)。 对于给定的2台处理机A 和B处理n 个作业，找出一个最优调度方案，使2台机器处理完这n个作业的时间最短。
编程任务：
对于给定的2台处理机A 和B处理n 个作业，找出一个最优调度方案，使2台机器处理
完这n 个作业的时间最短。
数据输入：
由文件input.txt提供输入数据。文件的第1行是1个正整数n, 表示要处理n个作业。接下来的2行中，每行有n 个正整数，分别表示处理机A 和B 处理第i 个作业需要的处理时间。
结果输出:
程序运行结束时，将计算出的最短处理时间输出到文件output.txt 中。
实验名称
独立任务最优调度问题
实验过程描述
程序代码
# 共有n个作业，a,b是机器处理作业需要时间的列表
# dp[i][j]表示处理前i个作业，机器A花费时间为j时，机器B的最小处理时间
def schedule(n, a, b):
sum_a = sum(a)
dp = [[float('inf')] * (sum_a + 1) for _ in range(n + 1)]
dp[0][0] = 0
for i in range(1, n + 1):
for j in range(sum_a + 1):
if j >= a[i - 1] and dp[i - 1][j - a[i - 1]] != float('inf'):
dp[i][j] = dp[i - 1][j - a[i - 1]] # A处理i
if dp[i - 1][j] != float('inf'):
dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[i - 1]) # B处理i
min_time = float('inf')
# 所有可能的j中，max(j, dp[n][j])的最小值
for j in range(sum_a + 1):
if dp[n][j] != float('inf'):
min_time = min(min_time, max(j, dp[n][j]))
return min_time
# 主程序
with open('input.txt', 'r') as f:
n = int(f.readline())
a = list(map(int, f.readline().split()))
b = list(map(int, f.readline().split()))
result = schedule(n, a, b)
with open('output.txt', 'w') as f:
f.write(str(result))
print("最短处理时间:", result)
测试用例
实验结果分析
本次实验实现了独立任务最优调度问题，两次测试用例分别对应的结果为49和192。
主要算法思路：
用动态规划设置一个dp数组，表示处理前i个作业，机器A花费时间为j时，机器B的最小处理时间（A，B也可以换顺序），然后下标从小到大遍历dp数组，对于每一个作业，有两种选择，a处理或者b处理，比较两者时间大小，选取花费时间较小的即可。而最终的结果，是对于所有a可能的处理时间中，也就是所有可能的j中，max(j, dp[n][j])的最小值。
时间复杂度分析：
双层循环，外层循环n次，内层循环sum_a+1次，所以时间复杂度为O(n*sum_a)
实验小结
问题
这道题在算法思路方面并没有特别大的问题，主要问题在于编写代码的过程中，如何去初始化dp数组，也就是语句
dp = [[float('inf')] * (sum_a + 1) for _ in range(n + 1)]
dp[0][0] = 0
首先考虑到dp数组一维大小要定义为机器A处理时间的最大值，也就是最坏情况当所有作业都由A来处理时；而数组的二维大小就是作业的总个数，这里的细节是遍历时要从1开始遍历，不然会出现数组下标错误。
体会
实践实现了动态规划算法的应用，主要语法学习点为使用float('inf')表示无穷大