-
Notifications
You must be signed in to change notification settings - Fork 0
/
子集和的目标值.cpp
56 lines (47 loc) · 1.06 KB
/
子集和的目标值.cpp
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
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#define MAXT 0x7fffffff
#define N 102
using namespace std;
struct store{
int goal;
int result;
};
vector<long long> in;
vector<store> record[N];
int minabs(int a, int b) {
if (a >= 0 && b >= 0) return min(a, b);
else if (a >= 0 && b<0) return min(a, -b);
else if (a<0 && b >= 0) return min(-a, b);
else if (a<0 && b<0) return min(-a, -b);
}
int f(int length, int goal) {
if (length == -1) {
if (goal<0) return 0 - goal;
else return goal;
}
// if (record[length][goal] != -1) return record[length][goal];
for(int i=0;i<record[length].size();i++){
if(record[length][i].goal==goal) return record[length][i].result;
}
store s;
s.goal=goal;
s.result= minabs(f(length - 1, goal), f(length - 1, goal - in.at(length)));
record[length].push_back(s);
return s.result;
//最后一个元素放不放在集合中
}
int main() {
int n, t;
cin >> n >> t;
for (int i = 0; i<n; i++) {
long long m;
cin >> m;
in.push_back(m);
}
int l = in.size();
cout << f(l - 1, t);
}