競技プログラミング用 知識集積所
ARC201B - Binary Knapsack
最終更新：
sport_programming
-
view
問題
必要知識
簡単な内容は省略
考え方
まず、重みw「以下」が扱いにくいので、適切な重みの価値0の荷物が十分な個数あると思って、重みw「ちょうど」にする問題として考える。
まず、重み1のものを考える。
wの2^0のビットが1の場合は品物を奇数個、ビットが0の場合は品物を偶数個、採用することになる。
この際、貪欲法（未作成）で考えると、単純に重い方から採用していけばよい。
ということは、奇数個採用の場合、重い順に並べて
wの2^0のビットが1の場合は品物を奇数個、ビットが0の場合は品物を偶数個、採用することになる。
この際、貪欲法（未作成）で考えると、単純に重い方から採用していけばよい。
ということは、奇数個採用の場合、重い順に並べて
- 1つ目は絶対に採用
- 2つ目と3つ目は、両方採用するか両方却下するかなので、2つまとめて重さ2の品物と扱ってよい
- 4つ目と5つ目は、両方採用するか両方却下するかなので、2つまとめて重さ2の品物と扱ってよい
- 以下略
となる。
偶数個採用の場合も、重い順に並べて
偶数個採用の場合も、重い順に並べて
- 1つ目と2つ目は、両方採用するか両方却下するかなので、2つまとめて重さ2の品物と扱ってよい
- 3つ目と4つ目は、両方採用するか両方却下するかなので、2つまとめて重さ2の品物と扱ってよい
- 以下略
となる。
その後で、今度は重み2の荷物（重さ1のものを2つセットにしたものを含む）を重い順に並べて同様にやる。
これを最終的に重み2^59の桁まで繰り返せばいい。
これを最終的に重み2^59の桁まで繰り返せばいい。
