工作指派问题（20 分） 设有 n 件工作， n 个人，每个人只能做一件工作，每件工作只能安排给一个 人，已知每个人做每件工作的耗费，请设计分支限界算法求解最少耗费的工作指 派。 要求： (1) 对问题进行分析； (9 分 ) (2) 给出分支限界算法的伪代码描述； (8 分 ) (3) 分析以上算法的时间复杂度。 (3 分 )对问题的分析： 我们有 n 种不同的食品，每种食品的加工时间为 ti，利润为 vi。我们需要在总加工时间不超过 T 的情况下选择加工食品，使得总利润最大。
状态表示:
设dp[i][j] 表示前 i 种食品在总时间不超过 j 时能够获得的最大利润。
状态转移方程:
dp[i][j]=max(dp[i−1][j],dp[i−1][j−ti]+vi)
其中：
- dp[i−1][j] 表示不选择第 �i 种食品时的最大利润。
- dp[i−1][j−ti]+vi 表示选择第 �i 种食品时的最大利润。
最小问题时的值:
初始条件：dp[0][j]=0，for all j 表示没有食品时，无论总时间为多少，利润都是 0。
伪代码：
Algorithm: Maximize Profit for Food Processing
Input: n (number of foods), T (maximum processing time), array t (processing times), array v (profits)
Output: Maximum profit
1. Initialize dp array of size (n+1) x (T+1) with all values set to 0
2. for i from 1 to n do
3. for j from 0 to T do
4. if j >= t[i-1] then
5. dp[i][j] = max(dp[i-1][j], dp[i-1][j-t[i-1]] + v[i-1])
6. else
7. dp[i][j] = dp[i-1][j]
8. return dp[n][T]
期末真题！！！非常重要，好久没有更新了，学校课程安排太紧凑了，考试集中，破防周！！！明天考算法了！！！（临阵磨枪嘿嘿嘿），大家祝我好运！！！
标签：复习,vi,规划法,笔记,算法,食品,ti,array,dp From： https://blog.csdn.net/2301_79582459/article/details/139741390