【算法设计与分析】实验——二维0-1背包问题（算法分析题：算法思路），独立任务最优调度问题（算法实现题：实验过程，描述，小结）

说明：博主是大学生，有一门课是算法设计与分析，这是博主记录课程实验报告的内容，题目是老师给的，其他内容和代码均为原创，可以参考学习，转载和搬运需评论吱声并注明出处哦。

要求：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] = 0for 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处理iif dp[i - 1][j] != float('inf'):dp[i][j] = min(dp[i][j], dp[i - 1][j] + b[i - 1])  # B处理imin_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')表示无穷大