Serviceを読んで理解し、同意したものとみなします。スタック・オーバーフローはプログラマーとプログラミングに熱心な人のためのQ&Aサイトです。133件0動的計画法を使ってナップサック問題を解きたいのですがなぜか不正解になります。?1から配列が始まっている(1origin)として解いてみようと思い下記のコードを書いてみたのですが正解になりません。超えないように選んだときの、価値の総和の最大値としていますが、これをi番目(i-1ではない)までの品物から重さがpを超えないように選ぶ時の価値の総和の最大値とすることはできるのでしょうか?https://atcoder.jp/contests/dp/tasks/dp_d問題文N個の品物があります。番号が振られています。太郎君は、N個の品物のうちいくつかを選び、ナップサックに入れて持ち帰ることにしました。Wであり、持ち帰る品物の重さの総和はW以下でなければなりません。太郎君が持ち帰る品物の価値の総和の最大値を求めてください。入力はすべて整数である。elseにあるchmaxは条件に関わらず行う必要があるのではないか(dp[i-1][p]が最も大きいかもしれない)といった点が気になりました。std::endl;}このコードでACすることを確認しました。ペアの配列への入力の仕方がおかしかったのだと思われます。dp[i-1][p])を入れなかった場合のコードのテストをしていないので、もしかしたらこの一行は無くてもACするかもしれません。私がDPの問題を解く時の癖で、DPを更新する上での「必要条件」としてのコードは書くようにしているというだけです...。番目の品物を使った場合の最小コストです。番目の品物を使えないので後者を考慮する必要はありませんが、そうでないときには両方を考慮する必要があるということです。|回答スタック・オーバーフローに参加してくれて、ありがとうございます!質問の回答を共有してください。回答を説明し、自分の検討結果も共有してください。意見を述べること(意見を述べるなら、参照リソース、自分の経験で意見をサポートしてください)さらにサポートが必要な場合このヘルプを参考してください。“回答を投稿”をクリックすることで利用規約、プライバシーポリシー、及びクッキーポリシーに同意したものとみなされます。タグが付いた他の質問を参照するか、自分で質問をする。質問のフィードこのRSSフィードを購読するには、このURLをコピーしてRSSリーダーに貼り付けてください。