Skip to content

Commit c1a56e5

Browse files
awangdevawangdev
committed
backpack
1 parent cff2343 commit c1a56e5

7 files changed

Lines changed: 751 additions & 476 deletions

File tree

‎Java/Backpack II.java‎

Lines changed: 149 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1,13 +1,15 @@
11
M
2+
1518497606
23

3-
做了Backpack I, 这个就如出一辙。
4-
想法还是，选了A[i-1] 或者没选A[i].
5-
一路往前跑不回头。就出来了。
6-
其实这个Backpack II 还更容易看懂代码。
4+
做了Backpack I, 这个就如出一辙, 只不过: dp存的不是w可否存成功true/false. dp存的是加上sum value的最大值.
5+
想法还是，选了A[i - 1] 或者没选A[i - 1]时候不同的value值.
76

87
O(m)的做法:
9-
想想，的确我们只care 最后一行，所以一个存value的就够了。
10-
注意：和bakcpackI的 O(m)一样的，j是倒序的。如果没有更好的j，就不要更新。就是这个道理。
8+
想想，的确我们只care 最后一行，所以一个存value的就够了.
9+
注意：和bakcpackI的 O(m)一样的，j是倒序的。如果没有更好的j，就不要更新。就是这个道理.
10+
11+
注意: 如果无法达到的w, 应该mark as impossible. 一种简单做法是mark as -1 in dp.
12+
如果有负数value, 就不能这样, 而是要开一个can[i][w]数组, 也就是backpack I 的原型.
1113

1214

1315
```
@@ -30,8 +32,149 @@
3032
LintCode Copyright Dynamic Programming Backpack
3133
*/
3234

35+
/*
36+
Thoughts:
37+
Dealing with value, the dp[i][w] = max value that can be formed over i tems at weight w.
38+
Two conditions:
39+
1. didn't pick A[i - 1]: dp[i - 1][w], value sum does not change.
40+
2. Picked A[i - 1]: dp[i - 1][w - A[i - 1]] + V[i - 1];
41+
Find the max of the above two, and record.
42+
Initialize with dp[0][0] = -1: not possible to form w, so mark as -1, impossible.
43+
*/
44+
45+
public class Solution {
46+
public int backPackII(int m, int[] A, int V[]) {
47+
if (A == null || V == null || A.length != V.length) {
48+
return 0;
49+
}
50+
int n = A.length;
51+
int[][] dp = new int[n + 1][m + 1]; // [5][5]
52+
53+
for (int j = 0; j <= m; j++) {
54+
dp[0][j] = -1; // 0 items cannot form weight j, hence value -1, marking impossible
55+
}
56+
dp[0][0] = 0; // 0 items, 0 weight -> 0 value
57+
58+
for (int i = 1; i <= n; i++) {
59+
for (int j = 1; j <= m; j++) {
60+
dp[i][j] = dp[i - 1][j]; // 0
61+
if (j - A[i - 1] >= 0 && dp[i - 1][j - A[i - 1]] != -1) {
62+
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
63+
}
64+
65+
}
66+
}
67+
68+
int rst = 0;
69+
for (int j = 0; j <= m; j++) {
70+
if (dp[n][j] != -1) {
71+
rst = Math.max(rst, dp[n][j]);
72+
}
73+
}
74+
return rst;
75+
}
76+
}
77+
78+
// Rolling array
79+
public class Solution {
80+
public int backPackII(int m, int[] A, int V[]) {
81+
if (A == null || V == null || A.length != V.length) {
82+
return 0;
83+
}
84+
int n = A.length;
85+
int[][] dp = new int[2][m + 1];
86+
for (int j = 0; j <= m; j++) {
87+
dp[0][j] = -1; // 0 items cannot form weight j, hence value -1, mark as impossible
88+
}
89+
dp[0][0] = 0; // 0 items, 0 weight -> 0 value
90+
int curr = 0, prev;
91+
92+
for (int i = 1; i <= n; i++) {
93+
// rolling index
94+
prev = curr;
95+
curr = 1 - prev;
96+
for (int j = 1; j <= m; j++) {
97+
dp[curr][j] = dp[prev][j]; // 0
98+
if (j - A[i - 1] >= 0 && dp[prev][j - A[i - 1]] != -1) {
99+
dp[curr][j] = Math.max(dp[curr][j], dp[prev][j - A[i - 1]] + V[i - 1]);
100+
}
101+
}
102+
}
103+
104+
int rst = 0;
105+
for (int j = 0; j <= m; j++) {
106+
if (dp[curr][j] != -1) {
107+
rst = Math.max(rst, dp[curr][j]);
108+
}
109+
}
110+
return rst;
111+
}
112+
}
113+
114+
115+
116+
117+
118+
/*
119+
Initialize with dp[0][0] = 0.
120+
This will pass the test, however it's not 100% explicit
121+
*/
122+
public class Solution {
123+
public int backPackII(int m, int[] A, int V[]) {
124+
if (A == null || V == null || A.length != V.length) {
125+
return 0;
126+
}
127+
int n = A.length;
128+
int[][] dp = new int[n + 1][m + 1]; // [5][5]
129+
dp[0][0] = 0; // 0 items, 0 weight -> 0 value
130+
for (int j = 0; j <= m; j++) {
131+
dp[0][j] = 0; // 0 items cannot form weight j, hence value 0
132+
}
133+
134+
for (int i = 1; i <= n; i++) {
135+
for (int j = 1; j <= m; j++) {
136+
dp[i][j] = dp[i - 1][j]; // 0
137+
if (j - A[i - 1] >= 0) {
138+
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - A[i - 1]] + V[i - 1]);
139+
}
140+
}
141+
}
142+
return dp[n][m];
143+
}
144+
}
145+
146+
// Rolling array
147+
public class Solution {
148+
public int backPackII(int m, int[] A, int V[]) {
149+
if (A == null || V == null || A.length != V.length) {
150+
return 0;
151+
}
152+
int n = A.length;
153+
int[][] dp = new int[2][m + 1]; // [5][5]
154+
dp[0][0] = 0; // 0 items, 0 weight -> 0 value
155+
for (int j = 0; j <= m; j++) {
156+
dp[0][j] = 0; // 0 items cannot form weight j, hence value 0
157+
}
158+
int curr = 0, prev;
159+
160+
for (int i = 1; i <= n; i++) {
161+
// rolling index
162+
prev = curr;
163+
curr = 1 - prev;
164+
for (int j = 1; j <= m; j++) {
165+
dp[curr][j] = dp[prev][j]; // 0
166+
if (j - A[i - 1] >= 0) {
167+
dp[curr][j] = Math.max(dp[curr][j], dp[prev][j - A[i - 1]] + V[i - 1]);
168+
}
169+
}
170+
}
171+
return dp[curr][m];
172+
}
173+
}
174+
33175

34176
/*
177+
Previous Notes.
35178
Thoughts:
36179
In Backpack I, we store true/false to indicate the largest j in last dp row.
37180
Here, we can store dp[i][j] == max value.

‎Java/Backpack III.java‎

Lines changed: 107 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,107 @@
1+
R
2+
1518502818
3+
4+
可以无限使用物品, 就失去了last i, last unique item的意义: 因为可以重复使用.
5+
6+
1. 所以可以转换一个角度: 用i种物品, 拼出w, 并且满足题目条件(max value).
7+
这里因为item i可以无限次使用, 所以要遍历使用了多少次K.
8+
9+
2. K虽然可以无限, 但是也被 k*A[i]所限制: 最大不能超过背包大小.
10+
11+
这样一来, 就close loop, 可以做了.
12+
13+
优化: Review
14+
降维: 需要画图review
15+
变成1个一位数组: 看双行的左右计算方向
16+
17+
```
18+
/*
19+
Given n kind of items with size Ai and value Vi( each item has an infinite number available)
20+
and a backpack with size m. What's the maximum value can you put into the backpack?
21+
22+
Notice
23+
You cannot divide item into small pieces and the total size of items you choose should smaller or equal to m.
24+
*/
25+
26+
/*
27+
Thoughts:
28+
Can pick any item for infinite times: there is no indicator of what's being picked last.
29+
We don't know which item && how many times it was picked.
30+
We should consider tracking: what type of items was picked how many times
31+
(consider once done with 1 type of item, move on to others and never re-pick)
32+
If A[i-1] was picked 0, 1, 2 ...., k times, then
33+
dp[i][w] = max{dp[i - 1][j - k*A[i - 1]] + k*V[i - 1]}, where k >= 0 -> infinite
34+
35+
Space: O(mn)
36+
Time: O(m * m * n) = O(nm^2)
37+
*/
38+
public class Solution {
39+
public int backPackIII(int[] A, int[] V, int m) {
40+
if (A == null || V == null || A.length != V.length) {
41+
return 0;
42+
}
43+
int n = A.length;
44+
int[][] dp = new int[n + 1][m + 1]; // max value with i items of weight w.
45+
for (int j = 0; j <= m; j++) {
46+
dp[0][j] = -1; // 0 items cannot form j weight, hence value = 0
47+
}
48+
dp[0][0] = 0;
49+
50+
for (int i = 1; i <= n; i++) {
51+
for (int j = 0; j <= m; j++) { // for all weight j at i items
52+
for (int k = 0; k * A[i - 1] <= m; k++) {
53+
if (j - k * A[i - 1] >= 0 && dp[i - 1][j - k * A[i - 1]] != -1) {
54+
dp[i][j] = Math.max(dp[i][j], dp[i - 1][j - k * A[i - 1]] + k * V[i - 1]);
55+
}
56+
}
57+
}
58+
}
59+
int rst = 0;
60+
for (int j = 0; j <= m; j++) {
61+
rst = Math.max(rst, dp[n][j]);
62+
}
63+
return rst;
64+
}
65+
}
66+
67+
68+
// Optimization
69+
// curve up
70+
/*
71+
dp[i][w] = max{dp[i - 1][j - k*A[i - 1]] + k*V[i - 1]}, where k >= 0 -> infinite
72+
1. Every position, we are adding k*V[i - 1]
73+
2. If we draw out how V[i-1] was being added alone with k = [0 ~ ...], we realize:
74+
the next i is basically: max{...all k's possibilities} + V[i - 1]
75+
So it reduces to:
76+
dp[i][w] = max{dp[i - 1][w], dp[i][w - A[i-1]] + V[i-1]}
77+
78+
*/
79+
80+
public class Solution {
81+
public int backPackIII(int[] A, int[] V, int m) {
82+
if (A == null || V == null || A.length != V.length) {
83+
return 0;
84+
}
85+
int n = A.length;
86+
int[][] dp = new int[n + 1][m + 1]; // max value with i items of weight w.
87+
for (int j = 0; j <= m; j++) {
88+
dp[0][j] = -1; // 0 items cannot form j weight, hence value = 0
89+
}
90+
dp[0][0] = 0;
91+
92+
for (int i = 1; i <= n; i++) {
93+
for (int j = 0; j <= m; j++) { // for all weight j at i items
94+
dp[i][j] = dp[i - 1][j];
95+
if (j - A[i - 1] >= 0) {
96+
dp[i][j] = Math.max(dp[i][j], dp[i][j - A[i - 1]] + V[i - 1]);
97+
}
98+
}
99+
}
100+
int rst = 0;
101+
for (int j = 0; j <= m; j++) {
102+
rst = Math.max(rst, dp[n][j]);
103+
}
104+
return rst;
105+
}
106+
}
107+
```

‎Java/Backpack.java‎

Lines changed: 13 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -1,36 +1,28 @@
11
M
22
1517903196
33

4+
考虑: 用i个item (可跳过地取), 是否能装到weight w?
45
需要从'可能性'的角度考虑, 不要搞成单一的最大值问题.
56

6-
1. 背包大小和总承重有关.
7-
2. 不要去找f[i]前i个物品的最大总重, 找的不是这个.
8-
f[i]及时找到可放的最大sum, 但是i+1可能有更好的值, 把f[i+1]变得更大更合适.
7+
1. 背包可装的物品大小和总承重有关.
8+
2. 不要去找dp[i]前i个物品的最大总重, 找的不是这个.
9+
dp[i]及时找到可放的最大sum, 但是i+1可能有更好的值, 把dp[i+1]变得更大更合适.
910

10-
DP.
11-
row是item大小: 0, A[0], A[1] ... A[A.length -1]
12-
col是背包累积的size: 0, 1, 2, ... m.
11+
boolean[][] dp[i][j]表示: 有前i个item, 用他们可否组成size为j的背包? true/false.
12+
(反过来考虑了，不是想是否超过size j, 而是考虑是否能拼出exact size == j)
13+
**注意**: 虽然dp里面一直存在i的位置, 实际上考虑的是在i位置的时候, 看前i-1个item.
1314

14-
想法：
15-
dp[i][j]有这么i-1个item, 用他们可否组成size为j的背包？true/false. （反过来考虑了，不是想是否超过size j， 而是考虑是否能拼出exact size == j）。
16-
注意注意：虽然dp里面一直存在i的位置，实际上考虑的是在i位置的时候，看前i-1个item.
15+
多项式规律:
16+
1. picked A[i-1]: 就是A[i-1]被用过, weight j 应该减去A[i-1]. 那么dp[i][j]就取决于dp[i-1][j-A[i-1]]的结果.
17+
2. did not pick A[i-1]: 那就是说, 没用过A[i-1], 那么dp[i][j]就取决于上一行d[i-1][j]
18+
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - A[i - 1]]
1719

18-
看一遍code，会发现：
19-
1. picked A[i-1]: 如果上一个item, A[i-1],被加了上来, 用j-A[i-1]看看，是否这再前一步也true. true就好啦。
20-
2. did not pick A[i-1]: 那就是说，不加上A[i-1], 上一行d[i-1][j]还是需要是true。
21-
22-
最后：
23-
跑一边dp 最下面一个row. 从末尾开始找，最末尾的一个j (能让dp[i][j] == true)的，就是最多能装的大小 :)
20+
结尾:
21+
跑一遍dp 最下面一个row. 从末尾开始找, 最末尾的一个j (能让dp[i][j] == true)的, 就是最多能装的大小 :)
2422

2523
时间，空间都是：O(mn)
2624

2725

28-
29-
再有：
30-
O(m)时间的做法，具体看solution. 注意j是倒序的啊！
31-
依然是O(mn)的空间
32-
33-
3426
```
3527
/*
3628
Given n items with size Ai, an integer m denotes the size of a backpack.

‎Java/Longest Palindromic Subsequence.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
/*
2+
Given a string s, find the longest palindromic subsequence's length in s.
3+
You may assume that the maximum length of s is 1000.
4+
5+
Example 1:
6+
Input:
7+
8+
"bbbab"
9+
Output:
10+
4
11+
One possible longest palindromic subsequence is "bbbb".
12+
Example 2:
13+
Input:
14+
15+
"cbbd"
16+
Output:
17+
2
18+
One possible longest palindromic subsequence is "bb".
19+
20+
*/

0 commit comments

Comments
 (0)