洛谷P 1049梱包問題(01リュック)

4423 ワード
水の問題ですが、久しぶりにブログを出したのを見て、改めてnoip普及グループt 4と見て、やりました.

タイトルリンク


https://www.luogu.org/problemnew/show/P1049

問題を解く構想.


裸の01リュックサックで、価値と重さに注意して1つのもので、最後に残りの体積を出力します.
勝手に二次元でACになって、一次元を書くのがおっくうだ.

ACコード

 1 #include
 2 #include
 3 #include
 4 #include
 5 #include
 6 #include
 7 #include
 8 #include<set>
 9 #include
10 #include
11 #include
12 #include
13 #include
14 using namespace std;
15 int n,v,w[35],dp[35][20005];
16 int main()
17 {
18     //freopen("","r",stdin);
19     //freopen("","w",stdout);
20     cin>>v>>n;
21     for(int i=1;i<=n;i++){
22         cin>>w[i];
23     }
24     for(int i=1;i<=n;i++){
25         for(int j=1;j<=v;j++){
26             if(j1][j];
27             else dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+w[i]);
28         }
29     }
30     cout<dp[n][v];
31     //fclose(stdin);
32     //fclose(stdout);
33     return 0;
34 }

///NOIP 2001普及グループt 4
Spark OFF_HEAP
TIL 22. JSクラスとJavaScript OOP