牛客網リュックサック問題

タイトルの説明
賀賀賀はジョージョーを連れて一緒に逃亡し、今ではジョージョーのバッグの中に入れるものがたくさんありますが、バッグの大きさは限られているので、私たちは中に非常に重要なものを入れることができます.今、この品物の数、体積、価値の数値を与えて、リュックサックの価値を最大にする方法を算出して、この数値を出力してほしいと思っています.ジョージョーはあなたに感謝します.
説明を入力:

 1  2   ，    n       v；

 2  i+1   3   ，  i      m、  w、  s。

出力の説明:

       ，               。

例1
入力
コピー

2 10
3 4 3
2 2 5

しゅつりょく
コピー

13

ダイナミックプランニング+バックパックの問題
c++コード:
#include
#include
using namespace std;
int main()
{int N,W;//はそれぞれ物品種数と体積cin>>N>>Wを表し、int m[2002]、w[2002]、s[2002];//はそれぞれある物品の数、体積を表し、価値for(int i=0;i cin>>m[i]>>w[i]>>s[i];int dp[2002]={0};//dp[]は前体積での最大価値for(int i=0;i for(int j=W;j>=w[i];j-=             for(int k=1;k<=m[i]&&k*w[i]<=j;k++)                 dp[j] = max(dp[j],dp[j-k*w[i]]+s[i]*k);     cout< }