Karp が分割問題に還元することにより、次の問題が NP 完全であることを示すことになっています。問題 X は、以下に従って、異なる年齢層にワクチンの用量を分配することです。
与えられた: D ワクチン用量、n 年齢グループ、入力としてa 1から a n 。ここで、年齢グループ k は入力としてd 1から d nのk 個の個人で構成され、年齢グループ k の各個人は d k用量、少なくとも tを受け取ります。各年齢層のkパーセントが完全にワクチン接種を受けている必要があり、残りの投与量の最大数は S.
この問題が NP 完全であることを証明する必要があります。ステップの 1 つは、この問題とパーティションの問題の間で Karp 削減を行うことです。私はさまざまな方法でこの削減を試みましたが、成功しませんでした。何か案は？擬似コードが理想的です。