私は解決したいこの問題を抱えています。n個のアイテムがあり、それぞれに値vが1行に配置されています。次に、k個の監視アイテムがあります。位置xの監視アイテムは、アイテムx-1、x、x+1を監視できます。私が計算したいのは、k人のスーパーバイザーが動的計画法を使用して監視できる最大値です。
例えば。n = {1,2,3,4} v = {7,10,5,8}これは、ポジション1-> 17のスーパーバイザーの合計値を意味します（n = 1および2をカバーできます）。
pos。2-> 22（n = 1,2,3をカバーできます）。
pos。3-> 23（n = 2,3,4をカバーできます）。
位置4->19（n = 3,4をカバーできます）。
では、特定の数のスーパーバイザーがカバーできる最大値を計算するにはどうすればよいでしょうか。
この例では、スーパーバイザーが1人の場合、最大値は23になり、2人の場合は36（1と4を選択）になります。その後、すべての項目がカバーされているため、これ以上のことはできません。
ナップサック問題を利用しようとしましたが、カバレッジの重複を解決する方法に行き詰まりました。
加重間隔スケジューリング問題も使用しようとしましたが、これは可能な最大値の合計を計算するためにのみ機能し、k間隔の最大値を計算するためには機能しません。
動的計画法でこの問題を解決する方法について得られるヒントにとても感謝しています。