Skip to content

Commit 1385cc6

Browse files
awangdevawangdev
committed
binary tree, backpack
1 parent 6e31be3 commit 1385cc6

6 files changed

Lines changed: 676 additions & 286 deletions

‎Java/Backpack II.java‎

Lines changed: 115 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,115 @@
1+
做了backpack I, 这个就如出一辙。
2+
想法还是，选了A[i-1] 或者没选A[i].
3+
一路往前跑不回头。就出来了。
4+
5+
O(m)的做法。想想，的确我们只care 最后一行，所以一个存value的就够了。 注意：和bakcpackI的 O(m)一样的，j是倒序的。如果没有更好的j，就不要更新。就是这个道理。
6+
7+
```
8+
/*
9+
Given n items with size Ai and value Vi, and a backpack with size m. What's the maximum value can you put into the backpack?
10+
11+
12+
Example
13+
Given 4 items with size [2, 3, 5, 7] and value [1, 5, 2, 4], and a backpack with size 10. The maximum value is 9.
14+
15+
Note
16+
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
17+
18+
Challenge
19+
O(n x m) memory is acceptable, can you do it in O(m) memory?
20+
21+
Tags Expand
22+
LintCode Copyright Dynamic Programming Backpack
23+
*/
24+
25+
26+
/*
27+
Thoughts:
28+
In Backpack I, we store true/false to indicate the largest j in last dp row.
29+
Here, we can store dp[i][j] == max value.
30+
31+
State:
32+
dp[i][j] : with i-1 items that fills exaclty size j, what's the max value
33+
34+
Fn:
35+
still, picked or did not picked A[i-1]
36+
1. Didn't pick. Value remains the same as if we didn't add A[i-1]
37+
2. Picked A[i - 1]. Hence, find out previous record dp[i-1][j - A[i - 1]], then add up the A[i-1] item's value V[i-1].
38+
3. Compare 1, and 2 for max value.
39+
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1])
40+
41+
Init:
42+
dp[0][0] = 0; // 0 item, fills size 0, and of course value -> 0
43+
44+
Return:
45+
dp[A.length][m]
46+
47+
Note:
48+
when creating dp, we do (A.length + 1) for row size, simply because we get used to checking A[i-1] for prevous record ... Just keep this style. Don't get confused.
49+
*/
50+
51+
52+
public class Solution {
53+
/**
54+
* @param m: An integer m denotes the size of a backpack
55+
* @param A & V: Given n items with size A[i] and value V[i]
56+
* @return: The maximum value
57+
*/
58+
public int backPackII(int m, int[] A, int V[]) {
59+
if (A == null || V == null || A.length == 0 || V.length == 0 || A.length != V.length || m <= 0) {
60+
return 0;
61+
}
62+
int[][] dp = new int[A.length + 1][m + 1];
63+
dp[0][0] = 0; // 0 item, to make pack size = 0, of course value = 0.
64+
65+
for (int i = 1; i <= A.length; i++) {
66+
for (int j = 0; j <= m; j++) {
67+
if (j - A[i - 1] >= 0) {
68+
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
69+
} else {
70+
dp[i][j] = dp[i - 1][j];
71+
}
72+
}
73+
}
74+
75+
return dp[A.length][m];
76+
}
77+
}
78+
79+
80+
/*
81+
To use just O(m) sapce.
82+
Just like in Backpack I, at the end, we only care about the last row. Why not just maintain a row, always keep the max value.
83+
84+
Note: Only update dp[j] if adding A[i-1] would be greater than current dp[j]
85+
86+
It's a bit hard to come up with this... but it's good exercise to build brain a bit.
87+
*/
88+
89+
public class Solution {
90+
91+
public int backPackII(int m, int[] A, int V[]) {
92+
if (A == null || V == null || A.length == 0 || V.length == 0 || A.length != V.length || m <= 0) {
93+
return 0;
94+
}
95+
int[]dp = new int[m + 1];
96+
dp[0] = 0; // 0 item, to make pack size = 0, of course value = 0.
97+
98+
for (int i = 1; i <= A.length; i++) {
99+
for (int j = m; j >= 0; j--) {
100+
if (j - A[i - 1] >= 0 && dp[j - A[i - 1]] + V[i - 1] > dp[j]) {
101+
dp[j] = dp[j - A[i - 1]] + V[i - 1];
102+
}
103+
}
104+
}
105+
106+
return dp[m];
107+
}
108+
}
109+
110+
111+
112+
113+
114+
115+
```

‎Java/Backpack.java‎

Lines changed: 115 additions & 45 deletions
Original file line numberDiff line numberDiff line change
@@ -1,3 +1,23 @@
1+
记得这个DP。
2+
row是item大小: 0, A[0], A[1] ... A[A.length -1]
3+
col是背包累积的size: 0, 1, 2, ... m.
4+
5+
想法是这样：
6+
dp[i][j]有这么i-1个item, 用他们可否组成size为j的背包？true/false. （反过来考虑了，不是想是否超过size j， 而是考虑是否能拼出exact size == j）。
7+
注意注意：虽然dp里面一直存在i的位置，实际上考虑的是在i位置的时候，看前i-1个item.
8+
看一遍code，会发现：
9+
1. picked A[i-1] 如果上一个item, A[i-1]被加了上来, 用j-A[i-1]看看，是否这再前一步也true. true就好啦！
10+
2. did not pick A[i-1]. 那就是说，不加上A[i-1], 上一行d[i-1][j]还是需要是true。
11+
12+
最后：
13+
跑一边dp 最下面一个row. 从末尾开始找，最末尾的一个j (能让dp[i][j] == true)的，就是最多能装的大小 :)
14+
15+
16+
17+
18+
再有：
19+
O(m)的做法，注意j是倒序的啊！
20+
```
121
/*
222
Given n items with size Ai, an integer m denotes the size of a backpack. How full you can fill this backpack?
323
@@ -17,20 +37,73 @@
1737
Tags Expand
1838
LintCode Copyright Dynamic Programming Backpack
1939
40+
41+
*/
42+
43+
/*
44+
Thoughts: Recap on 12.02.2015
45+
State
46+
DP[i][j]: i is the index of Ai, and j is the size from (0 ~ m).
47+
It means: depending if we added A[i-1], can we add up to j-space?Return ture/false.
48+
Note: that is, even j == 0, and I have a item with size == 2, I can still choose not to add, which means the backpack can reach j ==0. True.
49+
However, if we have a item with size == 2, but I need to fill space == 1.
50+
I will either pick/not pick item of size 2; either way, can't fill a backpack with size 1. False;
51+
Function:
52+
DP[i][j] = DP[i - 1][j] || DP[i - 1][j - A[i - 1]]; // based on if previous value is true/false: 1. didn't really add A[i-1] || 2. added A[i-1].
53+
Init:
54+
DP[0][0] = true; // 0 space and 0 items, true.
55+
All the rest are false;
56+
57+
Return the very last j that makes dp[A.length][j] true.
58+
*/
59+
60+
public class Solution {
61+
public int backPack(int m, int[] A) {
62+
if (A == null || A.length == 0 || m <= 0) {
63+
return 0;
64+
}
65+
boolean[][] dp = new boolean[A.length + 1][m + 1];
66+
dp[0][0] = true;
67+
68+
for (int i = 1; i <= A.length; i++) {
69+
for (int j = 0; j <= m; j++) {
70+
//added A[i - 1]
71+
if (j - A[i - 1] >= 0) {
72+
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]];
73+
} else {
74+
//not added A[i - 1];
75+
dp[i][j] = dp[i - 1][j];
76+
}
77+
}
78+
}
79+
80+
for (int j = m; j >= 0; j--) {
81+
if (dp[A.length][j]) {
82+
return j;
83+
}
84+
}
85+
return 0;
86+
}
87+
}
88+
89+
90+
91+
/*
2092
Thoughts:
2193
Well, I kind of forgot about how we did this in algorithm class, but here we go, after a bit research:
2294
DP[i][j] means: if i number of items in A, can we fill the bag size of j? Then, save a boolean in DP[i][j]. That means, if i items are too much for j?
2395
2496
So, there are two cases:
2597
1. A[i] is unfortunately too big to fit into size j, so skip item A[i] and use DP[i-1][j].
2698
2. OR, the other case: A[i] fits in well. We realize 2 things:
27-
a. first (i-1)th items much fit in well into the bag size of (j - A[i - 1]): DP[i-1][j - A[i-1]]. Basically says items must be fit in (true) before adding A[i]
28-
b. AND (j - A[i - 1]) must >= 0 to have space for next item i.
99+
a. first (i-1)th items much fit in well into the bag size of (j - A[i - 1]): DP[i-1][j - A[i-1]]. Basically says items must be fit in (true) before adding A[i]
100+
b. AND (j - A[i - 1]) must >= 0 to have space for next item i.
29101
30102
End:
31103
Iterate through j:(m ~ 0), and return j, if DP[A.length][j] is true. We are starting from m, because we need the largest number j.
32104
33105
This is 2D array version: memory mxn, space mxn
106+
34107
*/
35108

36109
public class Solution {
@@ -40,24 +113,24 @@ public class Solution {
40113
* @return: The maximum size
41114
*/
42115
public int backPack(int m, int[] A) {
43-
if (A == null || m == 0) {
44-
return 0;
45-
}
46-
47-
boolean[][] DP = new boolean[A.length + 1][m + 1];
48-
DP[0][0] = true;
49-
for (int i = 1; i <= A.length; i++) {
50-
for (int j = 0; j <= m; j++) {
51-
DP[i][j] = DP[i - 1][j] || (j - A[i - 1] >= 0 && DP[i - 1][j - A[i - 1]]);
52-
}
53-
}
54-
55-
for (int j = m; j >= 0; j--) {
56-
if (DP[A.length][j]) {
57-
return j;
58-
}
59-
}
60-
return 0;
116+
if (A == null || m == 0) {
117+
return 0;
118+
}
119+
120+
boolean[][] DP = new boolean[A.length + 1][m + 1];
121+
DP[0][0] = true;
122+
for (int i = 1; i <= A.length; i++) {
123+
for (int j = 0; j <= m; j++) {
124+
DP[i][j] = DP[i - 1][j] || (j - A[i - 1] >= 0 && DP[i - 1][j - A[i - 1]]);
125+
}
126+
}
127+
128+
for (int j = m; j >= 0; j--) {
129+
if (DP[A.length][j]) {
130+
return j;
131+
}
132+
}
133+
return 0;
61134
}
62135
}
63136

@@ -77,31 +150,28 @@ public int backPack(int m, int[] A) {
77150
*/
78151

79152
public class Solution {
80-
/**
81-
* @param m: An integer m denotes the size of a backpack
82-
* @param A: Given n items with size A[i]
83-
* @return: The maximum size
84-
*/
85153
public int backPack(int m, int[] A) {
86-
if (A == null || m == 0) {
87-
return 0;
88-
}
89-
90-
boolean[] DP = new boolean[m + 1];
91-
DP[0] = true;
92-
for (int i = 1; i <= A.length; i++) {
93-
for (int j = m; j >= 0; j--) {
94-
if (j - A[i - 1] >= 0 && DP[j - A[i - 1]]) {
95-
DP[j] = DP[j - A[i - 1]];
96-
}
97-
}
98-
}
99-
100-
for (int j = m; j >= 0; j--) {
101-
if (DP[j]) {
102-
return j;
103-
}
104-
}
105-
return 0;
154+
if (A == null || m == 0) {
155+
return 0;
156+
}
157+
158+
boolean[] DP = new boolean[m + 1];
159+
DP[0] = true;
160+
for (int i = 1; i <= A.length; i++) {
161+
for (int j = m; j >= 0; j--) {
162+
if (j - A[i - 1] >= 0 && DP[j - A[i - 1]]) {
163+
DP[j] = true;
164+
}
165+
}
166+
}
167+
168+
for (int j = m; j >= 0; j--) {
169+
if (DP[j]) {
170+
return j;
171+
}
172+
}
173+
return 0;
106174
}
107175
}
176+
177+
```

0 commit comments

Comments
 (0)