Problem
質量が m1, …, mN でコストが c の N 個のアイテムがあるとします。 < sub>1, …, cN それぞれ.
M以下の重量に耐えられるバックパックに詰め込みます。コストが最も高いバックパックで運べるアイテムのセットを決定します。
入力:
- 最初の行には、100 を超えない自然数 N と 10000 を超えない自然数 M が含まれています;
- 2 行目に N 個の自然数 mi を 100 を超えないように入力してください;
- N 個の自然数 withi が 100 個を超えない 3 行目に入力します。
出力: コストが最も高いバックパックに含まれるアイテムの数 (1 から N までの数字) を出力します (1 行に 1 つの数字) .
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
4 6
2 4 1 2
7 2 5 1
|
1
3
4 |