演算法›Ch3 動態規劃
第 26 題/共 40 題
◀ AL 26/40
26. 0/1 Knapsack、Dynamic Programming
#AL-03-026易0/1 KnapsackDynamic Programming

We aim to select courses from a pool of nn courses. Since this is still in the planning phase, each course has no specified start or finish times. Each course ii is characterized by its duration pip_i and weight wiw_i. The total available classroom time is CC. We want to identify a subset of courses S⊆{1,…,n}S \subseteq \{1, \ldots, n\} such that the total duration of courses in SS does not exceed CC and the total weight of SS is maximized. To achieve this, we have developed a dynamic programming algorithm that uses a (n+1)×(C+1)(n+1) \times (C+1) table T[0:n,0:C]T[0:n, 0:C] to solve the problem. Here, T[i,j]T[i,j] represents the maximum total weight achievable when considering only the subset of courses {1,…,i}\{1, \ldots, i\} and a classroom available for jj units of time. Write the recursive formula to compute T[i,j]T[i,j].

📄 成大114
跳轉到第題
▤完整推導請見《WH 資工筆記 · 演算法》Ch3 動態規劃
本章題號 · 21–40 / 40