backPack problems

backPack

http://www.lintcode.com/zh-cn/problem/backpack/

method 1

1
2
3
4
5
6
7
8
9
10
11
12
13
int backPack(int m, vector<int> A) {
vector<int> f(m + 1, 0);
for (int i = 0; i < A.size(); i++) {
for (int j = m; j >= 0; j--) {
if (j >= A[i]) {
f[j] = max(f[j], f[j - A[i]] + A[i]);
}
}
}
return f[m];
}

method 2

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
int backPack(int m, vector<int> A) {
vector<bool> f(m + 1, false);
f[0] = true;
for (int i = 0; i < A.size(); i++) {
for (int j = m; j >= 0; j--) {
if (j >= A[i]) {
f[j] = f[j] || f[j - A[i]];
}
}
}
for (int j = m; j >= 0; j--) {
if (f[j]) {
return j;
}
}
return 0;
}

backPackII

http://www.lintcode.com/zh-cn/problem/backpack-ii/

cpp code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int backPackII(int m, vector<int> A, vector<int> V) {
// f[i][j] = max(f[i - 1][j], f[i - 1][j - A[i] ] + V[i])
vector<int> f(m + 1, 0);
for (int i = 0; i < A.size(); i++) {
for (int j = m; j >= 0; j--) {
if (j >= A[i] && (f[j] < f[j - A[i]] + V[i])) {
f[j] = f[j - A[i]] + V[i];
}
}
}
return f[m];
}