Submission #02176

ソースコード

?
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
#include<bits/stdc++.h>
using namespace std;
int n, W, v[100], w[100];
int dp[100][10001], Next[100][10001];
int knapsack(int idx, int weight)
{
if(idx == n) return(0);
if(~dp[idx][weight]) return(dp[idx][weight]);
int ret = 0, buffer;
if(weight >= w[idx]) {
buffer = knapsack(idx + 1, weight - w[idx]);
Next[idx][weight] = weight - w[idx];
ret = buffer + v[idx];
}
buffer = knapsack(idx + 1, weight);
if(buffer > ret) {
ret = buffer;
Next[idx][weight] = weight;
}
return(dp[idx][weight] = ret);
}
int main()
{
memset(dp, -1, sizeof(dp));
memset(Next, -1, sizeof(Next));
cin >> n >> W;
for(int i = 0; i < n; i++) {
cin >> v[i] >> w[i];
}
cout << knapsack(0, W) << endl;
int weight = W;
bool first = false;
for(int i = 0; i < n; i++) {
if(Next[i][weight] < 0) {
break;
} else if(weight != Next[i][weight]) {
if(first++) cout << " ";
cout << i + 1;
}
weight = Next[i][weight];
}
cout << endl;
}

ステータス

項目 データ
問題 0240 - ナップザック問題(Expert)
ユーザー名 ei1333
投稿日時 2015-12-11 18:30:31
言語 C++11
状態 Accepted
得点 7
ソースコード長 1057 Byte
最大実行時間 22 ms
最大メモリ使用量 8548 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
DPL_1_B_in1.txt AC 13 ms 8284 KB
1
DPL_1_B_in2.txt AC 15 ms 8392 KB
1
DPL_1_B_in3.txt AC 17 ms 8472 KB
1
DPL_1_B_in4.txt AC 13 ms 8504 KB
1
DPL_1_B_in5.txt AC 14 ms 8476 KB
1
DPL_1_B_in6.txt AC 12 ms 8448 KB
1
DPL_1_B_in7.txt AC 13 ms 8548 KB
1
DPL_1_B_in8.txt AC 13 ms 8396 KB
1
DPL_1_B_in9.txt AC 12 ms 8372 KB
1
DPL_1_B_in10.txt AC 16 ms 8260 KB
1
DPL_1_B_in11.txt AC 15 ms 8368 KB
1
DPL_1_B_in12.txt AC 15 ms 8344 KB
1
DPL_1_B_in13.txt AC 16 ms 8316 KB
1
DPL_1_B_in14.txt AC 14 ms 8424 KB
1
DPL_1_B_in15.txt AC 17 ms 8264 KB
1
DPL_1_B_in16.txt AC 15 ms 8360 KB
1
DPL_1_B_in17.txt AC 14 ms 8336 KB
1
DPL_1_B_in18.txt AC 14 ms 8316 KB
1
DPL_1_B_in19.txt AC 13 ms 8296 KB
1
DPL_1_B_in20.txt AC 13 ms 8364 KB
1
DPL_1_B_in21.txt AC 15 ms 8464 KB
1
DPL_1_B_in22.txt AC 13 ms 8312 KB
1
DPL_1_B_in23.txt AC 15 ms 8420 KB
1
DPL_1_B_in24.txt AC 18 ms 8388 KB
1
DPL_1_B_in25.txt AC 13 ms 8360 KB
1
DPL_1_B_in26.txt AC 14 ms 8460 KB
1
DPL_1_B_in27.txt AC 14 ms 8304 KB
1
DPL_1_B_in28.txt AC 13 ms 8408 KB
1
DPL_1_B_in29.txt AC 17 ms 8380 KB
1
DPL_1_B_in30.txt AC 16 ms 8444 KB
1
DPL_1_B_in31.txt AC 20 ms 8412 KB
1
DPL_1_B_in32.txt AC 22 ms 8516 KB
1
DPL_1_B_in33.txt AC 16 ms 8488 KB
1
DPL_1_B_in34.txt AC 17 ms 8332 KB
1
DPL_1_B_in35.txt AC 17 ms 8432 KB
1
DPL_1_B_in36.txt AC 22 ms 8404 KB
1