问题：
将若干体积不同的物品放入背包中，是否能使的背包恰好放满 例如：背包容量为16 物品体积： 3 4 5 6 7 答案：true
思路：
用一个二维数组来表示前n件物品组合是否放满指定容量大小的背包， 例如：bag[2][3]表示前两件物品的选择方式有没有可能放满容量为3的背包 设：i 为物品编号，cost[ i ]表示第i件物品所代表的体积；j为容量 状态转移方程：bag[ i ][ j ] = bag[ i-1 ][ j ] OR bag[ i-1 ][ j-cost[ i ] ]； 出口： 1.只考虑第一件物品时，当且仅当背包容量和物品所占体积刚好相等时，bag[][]为True。 2.当物品体积大于容量时，bag[][]值为false 3.当容量有剩余使，bag[][]值为false
代码：
private static boolean fillBag(int[] cost
, int capacity
) {
int rows
= cost
.length
+ 1;
int cols
= capacity
+ 1;
boolean[][] bag
= new boolean[rows
][cols
];
boolean choose
, notChoose
;
for (int i
= 0; i
< rows
; i
++) {
bag
[i
][0] = false;
}
for (int i
= 0; i
< cols
; i
++) {
bag
[0][i
] = false;
}
for (int i
= 1; i
< cols
; i
++) {
bag
[0][i
] = false;
if (i
== cost
[1]) {
bag
[1][i
] = true;
}
}
for (int i
= 2; i
< rows
; i
++) {
for (int j
= 1; j
< cols
; j
++) {
if (cost
[i
-1] > j
) {
bag
[i
][j
] = false;
} else {
choose
= bag
[i
- 1][j
- cost
[i
-1]];
notChoose
= bag
[i
- 1][j
];
bag
[i
][j
] = choose
|| notChoose
;
}
}
}
return bag
[rows
- 1][cols
- 1];
}
