P2515 [HAOI2010] Software Installation

We have $N$ software packages. For a software $i$, it occupies $W_i$ units of disk space, and its value is $V_i$. We want to choose some software to install on a computer with disk capacity $M$, so that the total value of the installed software is as large as possible (i.e., the sum of $V_i$ is maximized). However, there is a problem: there are dependency relationships between software. Software $i$ can work properly only if software $j$ (including software $j$’s direct or indirect dependencies) is installed (software $i$ depends on software $j$). Fortunately, a software depends on at most one other software. If a software cannot work properly, then its contribution is $0$. We already know the dependencies between software: software $i$ depends on $D_i$. Please design a plan to install software so that the total value is as large as possible. Each software can be installed at most once. If a software has no dependency, then $D_i=0$; in this case, as long as this software is installed, it will work properly.

Line 1: $N,M(0\leq N\leq 100, 0\leq M\leq 500)$ Line 2: $W_1,W_2, ... W_i, ..., W_n (0\leq W_i\leq M)$ Line 3: $V_1, V_2, ..., V_i, ..., V_n (0\leq V_i\leq 1000)$ Line 4: $D_1, D_2, ..., D_i, ..., D_n (0\leq D_i\leq N, D_i≠i)$

An integer representing the maximum total value.

Translated by ChatGPT 5