Problem
Cho N vật phẩm có khối lượng m1, …, mN và chi phí c < sub>1, …, cN tương ứng.
Họ lấp đầy một chiếc ba lô có thể chịu được trọng lượng không quá M. Xác định tập hợp các mặt hàng có thể mang theo trong ba lô có chi phí cao nhất.
Đầu vào:
- dòng đầu tiên chứa số tự nhiên N không quá 100 và số tự nhiên M không quá 10000;
- ở dòng thứ hai nhập N các số tự nhiên mi không quá 100;
- N các số tự nhiên vớii không vượt quá 100 được nhập vào dòng thứ ba.
Đầu ra: in số lượng vật phẩm (số từ 1 đến N) sẽ được đưa vào ba lô có giá cao nhất (một số trên mỗi dòng) .
Ví dụ
<đầu>
| # |
Đầu vào |
Đầu ra |
| 1 |
4 6
2 4 1 2
7 2 5 1
|
1
3
4 |