Problem
Diberikan N item berjisim m1, …, mN dan kos c < sub>1, …, cN masing-masing.
Mereka mengisi beg galas yang boleh menahan berat tidak lebih daripada M. Tentukan set item yang boleh dibawa dalam beg galas yang mempunyai kos tertinggi.
Input:
- baris pertama mengandungi nombor asli N tidak melebihi 100 dan nombor asli M tidak melebihi 10000;
- pada baris kedua masukkan N nombor asli mi tidak melebihi 100;
- N nombor asli dengani tidak melebihi 100 dimasukkan dalam baris ketiga.
Output: cetak nombor item (nombor dari 1 hingga N) yang akan dimasukkan ke dalam beg galas dengan kos tertinggi (satu nombor setiap baris) .
Contoh
| # |
Input |
Output |
| 1 |
4 6
2 4 1 2
7 2 5 1
|
1
3
4 |