Backpack
Description
Given n items with size Ai, an integer m denotes the size of a backpack.
How full you can fill this backpack?
Notice
You can not divide any item into small pieces.
Example
If we have 4 items with size [2, 3, 5, 7], the backpack size is 11, we can select [2, 3, 5],
so that the max size we can fill this backpack is 10.
If the backpack size is 12. we can select [2, 3, 7] so that we can fulfill the backpack.
You function should return the max size we can fill in the given backpack.
Challenge
O(n x m) time and O(m) memory.
O(n x m) memory is also acceptable if you do not know how to optimize memory.
解题思路
背包问题：单次选择+最大体积。
一、二维状态
- 定义状态：定义
f[i][j]为A的前i个数是否能填满大小为j的背包。 - 定义状态转移函数：对于当前状态
f[i][j]，- 如果不计入
A[i - 1]，则f[i][j]对应的上一个状态是f[i - 1][j]； - 如果计入
A[i - 1]，满足条件j>= A[i - 1]，那么f[i][j]上一个状态是f[i - 1][j - A[i - 1]] - 以上两种情况满足其一即可。
- 如果不计入
- 定义起点：
- 对于二维的动规问题，
f[i][0]和f[0][j]都是边界条件，需要进行初始化，初始化时要同时注意边界的状态转移。 - 当
i != 0，j == 0时，如果一个数字都不计入，即取前i个数字中的零个，那么可得结果为零，所以f[i][0]的状态为true。 - 当
i == 0，j != 0时，前零个元素的和显然无法得到值j，f[0][j]状态为false。 f[0][0]状态为true。
- 对于二维的动规问题，
- 定义终点：最终结果即为
f[n][m]。 注：初始化时也需要注意取值范围是数组长度加一。
易错点：
- 状态函数
f[][]的初始化范围为boolean[][] f = new boolean[n + 1][m + 1];。- 双重循环的起始值，结束值。
j和A[i - 1]之间的关系，可以等于。
算法复杂度
- 时间复杂度：
O(n*m)。 - 空间复杂度：
O(n*m)。
Java 实现
public
class
Solution
{
/**
*
@param
m: An integer m denotes the size of a backpack
*
@param
A: Given n items with size A[i]
*
@return
: The maximum size
*/
public
int
backPack
(
int
m,
int
[] A)
{
if
(A ==
null
|| A.length ==
0
) {
return
0
;
}
int
n = A.length;
// state
boolean
[][] f =
new
boolean
[n +
1
][m +
1
];
// initialize
f[
0
][
0
] =
true
;
for
(
int
i =
1
; i
<
= n; i++) {
for
(
int
j =
0
; j
<
= m; j++) {
f[i][j] = f[i -
1
][j] || (j
>
= A[i -
1
]
&
&
f[i -
1
][j - A[i -
1
]]) ;
}
}
// answer
for
(
int
j = m; j
>
=
0
; j--) {
if
(f[n][j]) {
return
j;
}
}
return
0
;
}
}
使用滚动数组优化空间，可使空间复杂度降至O(m)。
public
class
Solution
{
/**
*
@param
m: An integer m denotes the size of a backpack
*
@param
A: Given n items with size A[i]
*
@return
: The maximum size
*/
public
int
backPack
(
int
m,
int
[] A)
{
if
(m
<
=
0
|| A ==
null
|| A.length ==
0
) {
return
0
;
}
int
n = A.length;
// status
boolean
[][] f =
new
boolean
[
2
][m +
1
];
// initialize
f[
0
][
0
] =
true
;
for
(
int
i =
1
; i
<
= m; i++) {
f[
0
][i] =
false
;
}
for
(
int
i =
1
; i
<
= n; i++) {
f[i %
2
][
0
] =
true
;
for
(
int
j =
1
; j
<
= m; j++) {
f[i %
2
][j] = f[(i -
1
) %
2
][j] ||
((A[i-
1
]
<
= j)
&
&
f[(i -
1
) %
2
][j - A[i -
1
]]);
}
}
int
res =
0
;
for
(
int
i = m; i
>
=
0
; i--) {
if
(f[n %
2
][i]) {
res = i;
break
;
}
}
return
res;
}
}
二、一维状态
- 定义状态：定义
f[j]为A的前i个数是否能填满大小为j的背包。 - 定义状态转移函数：对于当前状态
f[j]，- 如果不计入
A[i - 1]，则f[j]保持状态不变； - 如果计入
A[i - 1]，满足条件j>A[i - 1]，那么f[j]上一个状态是f[j - 1] - 注意题目中的 隐含条件为每个数只能使用一次 。在使用二维数组定义状态是，其中一个维度避免了同一个数字的重复使用。所以在使用一维状态转移函数时，要避免出现这种情况，在内循环的取值需要从大到小。
- 如果不计入
- 定义起点：
f[0]状态为true。
- 定义终点：最终结果即为
f[m]。
算法复杂度
- 时间复杂度：
O(nm)。 - 空间复杂度：
O(m)。
Java 实现
public
class
Solution
{
/**
*
@param
m: An integer m denotes the size of a backpack
*
@param
A: Given n items with size A[i]
*
@return
: The maximum size
*/
public
int
backPack
(
int
m,
int
[] A)
{
if
(A ==
null
|| A.length ==
0
) {
return
0
;
}
int
n = A.length;
// state
boolean
[] f =
new
boolean
[m +
1
];
// initialize
f[
0
] =
true
;
for
(
int
i =
1
; i
<
= n; i++) {
// j starts from m to avoid repeating use of iterm A[i - 1]
for
(
int
j = m; j
>
=
0
; j--) {
if
(j
>
= A[i -
1
]
&
&
f[j - A[i -
1
]]) {
f[j] = f[j - A[i -
1
]];
}
}
}
// answer
for
(
int
j = m; j
>
=
0
; j--) {
if
(f[j]) {
return
j;
}
}
return
0
;
}
}