Submission #67912

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include<bits/stdc++.h>
using namespace std;
int main(){
int n,w;
cin >> n >> w;
vector<vector<int>> judge(n+10,vector<int>(10010,0)); // 添字で重さを表現するために配列の要素を、最大の重さ分用意する。
vector<int> cost(n);
vector<int> weight(n);
// 重さとコストを管理し易いように、別別の配列を確保しておく
for(int i=0;i<n;i++){
cin >> cost[i] >> weight[i];
}
for(int i = 0;i < n;i++){ //見る商品が、何個まで選べるかを指定する添字
// 直前までの配列に、仮定の最大値を格納してあるため、その値を引用する。
for(int j = 0;j <= w;j++){
if(weight[i]<=j){ // 今見たい重さが、許容される重さであるかどうか(1ループ内で、何度も許容される重さが繰り返されるためOK)
judge[i+1][j] = max(judge[i][j],judge[i][j - weight[i]] + cost[i]); // 次に遷移する先の値を決めようとしている。
// 値の更新がなければ、最大が決まっている現在地点のコストを持ってくる。
// 値の更新があれば、今見ている重さの分のコストを最大値として持ってきたい。
// |
// +-> ？なぜ重さを示す添字がいま見ている商品の重さを引いているのか？
// | +-> A, 今見ている商品型されたという結果に変えたい。
// | 従って、現在の重さを足す前の合計コストから持ってこなければ、
// | シュミレーション対象ではない値が足されてしまう。
// +-> ?コストを更新するためとはいえ、重さの添字から、対象商品の重さを引いてしまうと、正確な値が反映されないのでは?
// +-> 解釈1.このDPは、全シュミレートを行うため、全パターン見ているからヨシ！
// +-> 解釈2.そもそも、値の更新があったということは、新しい商品を詰もうとしている！直前までの最大コストと比べて
// 値の更新というアクションを起こそうというのであれば、それはつまりこの商品を足した方が、直前までで
// 今の重さよりも小さい商品を足した時のコストの合計よりも、この商品の方が相応しい商品であるということ！
/* --< ! ForExample ! >--
+----------------------------------------------------------+
コスト| 01 03 05 07 12 36 37 38 39 40 44 45 45 45 45 45 45 45 45
|-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.
重さ | 01 02 03 04 05 06 07 08 09 10 11 12 12 12 12 12 12 12 12
+----------------------------------------------------------+
この↑の場合は重さが12の場合でコストが頭打ちになってしまった場合。
では、ここに13個めの商品として重さ2がのコストが54の偉大な商品をラインナップに加えてみる。
すると、
+-----値を遷移するために見た場所がここ！
| +=====ほらっ！値がしっかり最大値になっている。
| |
v v
+----------------------------------------------------------+
コスト| 01 03 05 07 12 36 37 38 39 40 44 45 45 45 99 99 99 99 99
|-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.-.
重さ | 01 02 03 04 05 06 07 08 09 10 11 12 12 12 15 15 15 15 15
+----------------------------------------------------------+
このように、値が崩れることはありません（違っていたらすいません。納得させるために、分かり易いパターンを選択しました。）
*/
}else{
judge[i+1][j] = judge[i][j];
}
}
}
cout << judge[n][w] << endl;
return(0);
}

ステータス

項目 データ
問題 0238 - ナップザック問題(Easy)
ユーザー名 <span style="color:#000000;font-weight:bold;">ei2031</span>
投稿日時 2021-08-03 14:00:55
言語 C++17
状態 Accepted
得点 3
ソースコード長 4023 Byte
最大実行時間 31 ms
最大メモリ使用量 5024 KB

セット

セット 得点 Cases
1 ALL 3 / 3 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 23 ms 1116 KB
1
DPL_1_B_in2.txt AC 18 ms 992 KB
1
DPL_1_B_in3.txt AC 28 ms 1244 KB
1
DPL_1_B_in4.txt AC 22 ms 1216 KB
1
DPL_1_B_in5.txt AC 18 ms 1196 KB
1
DPL_1_B_in6.txt AC 18 ms 1176 KB
1
DPL_1_B_in7.txt AC 21 ms 1804 KB
1
DPL_1_B_in8.txt AC 23 ms 1840 KB
1
DPL_1_B_in9.txt AC 20 ms 1876 KB
1
DPL_1_B_in10.txt AC 15 ms 1784 KB
1
DPL_1_B_in11.txt AC 23 ms 1568 KB
1
DPL_1_B_in12.txt AC 19 ms 1604 KB
1
DPL_1_B_in13.txt AC 20 ms 1768 KB
1
DPL_1_B_in14.txt AC 21 ms 1932 KB
1
DPL_1_B_in15.txt AC 23 ms 1908 KB
1
DPL_1_B_in16.txt AC 21 ms 1876 KB
1
DPL_1_B_in17.txt AC 17 ms 952 KB
1
DPL_1_B_in18.txt AC 27 ms 1348 KB
1
DPL_1_B_in19.txt AC 24 ms 1136 KB
1
DPL_1_B_in20.txt AC 19 ms 1352 KB
1
DPL_1_B_in21.txt AC 23 ms 2932 KB
1
DPL_1_B_in22.txt AC 17 ms 2956 KB
1
DPL_1_B_in23.txt AC 22 ms 2848 KB
1
DPL_1_B_in24.txt AC 21 ms 2868 KB
1
DPL_1_B_in25.txt AC 19 ms 4928 KB
1
DPL_1_B_in26.txt AC 21 ms 4904 KB
1
DPL_1_B_in27.txt AC 25 ms 5012 KB
1
DPL_1_B_in28.txt AC 19 ms 4864 KB
1
DPL_1_B_in29.txt AC 31 ms 4848 KB
1
DPL_1_B_in30.txt AC 29 ms 4812 KB
1
DPL_1_B_in31.txt AC 25 ms 4916 KB
1
DPL_1_B_in32.txt AC 23 ms 5024 KB
1
DPL_1_B_in33.txt AC 26 ms 5000 KB
1
DPL_1_B_in34.txt AC 23 ms 4856 KB
1
DPL_1_B_in35.txt AC 28 ms 4960 KB
1
DPL_1_B_in36.txt AC 27 ms 4944 KB
1