演算法›Ch3 動態規劃第 26 題/共 40 題
26. 0/1 Knapsack、Dynamic Programming
#AL-03-026易0/1 KnapsackDynamic Programming
We aim to select courses from a pool of courses. Since this is still in the planning phase, each course has no specified start or finish times. Each course is characterized by its duration and weight . The total available classroom time is . We want to identify a subset of courses such that the total duration of courses in does not exceed and the total weight of is maximized. To achieve this, we have developed a dynamic programming algorithm that uses a table to solve the problem. Here, represents the maximum total weight achievable when considering only the subset of courses and a classroom available for units of time. Write the recursive formula to compute .
📄 成大114
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃