Cái túi có vật phẩm phụ thuộc
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
graph
Đề bài
Có $N$ vật phẩm được đánh số từ $1$ đến $N$. Vật phẩm thứ $i$ có giá tiền $w_i$, độ quan trọng $v_i$, và chỉ số phụ thuộc $q_i$:
- Nếu $q_i = 0$, vật phẩm $i$ là món chính.
- Nếu $q_i > 0$, vật phẩm $i$ là phụ kiện đi kèm của món chính $q_i$. Bạn chỉ có thể mua phụ kiện nếu đã mua món chính tương ứng.
Với ngân sách $W$, hãy chọn mua các vật phẩm sao cho tổng giá tiền không vượt quá $W$ và tổng độ quan trọng là lớn nhất.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, W$ ($1 \le N \le 60$, $1 \le W \le 10^4$).
- $N$ dòng tiếp theo, dòng thứ $i$ chứa ba số nguyên $w_i, v_i, q_i$ ($1 \le w_i \le 10^4$, $1 \le v_i \le 10^6$, $0 \le q_i \le N$). Dữ liệu đảm bảo nếu $q_i > 0$ thì vật phẩm $q_i$ là món chính ($q_{q_i} = 0$).
Dữ liệu ra
Một số nguyên duy nhất là tổng độ quan trọng lớn nhất.
Ví dụ
| Input | Output |
|---|---|
5 10<br>8 16 0<br>4 8 1<br>3 9 1<br>4 12 0<br>5 10 0 |
22 |
Giới hạn
- $1 \le N \le 60$
- $1 \le W \le 10^4$
Community Discussion