当前位置 博文首页 > 数据结构和算法：LeetCode 1049. 最后一块石头的重量 II
截止到目前我已经写了 500多道算法题，其中部分已经整理成了pdf文档，目前总共有1000多页（并且还会不断的增加），大家可以免费下载
下载链接：https://pan.baidu.com/s/1hjwK0ZeRxYGB8lIkbKuQgQ
提取码：6666
if (j >= stones[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
} else {
//背包容量已经放不下了
dp[i][j] = dp[i - 1][j];
}
6}
但这道题并不是让求背包的最大容量，前面我们分析的是把数组分为两组，如果一组的值是x，那么另一组的值就是sum-x，他们的差值就是(sum-x)-x；这个就是我们要求的值，而x就是上面我们所求的背包的最大容量。
我们来看下最终代码
public int lastStoneWeightII(int[] stones) {
int length = stones.length;
int sum = 0;
for (int num : stones) {
sum += num;
}
//背包的容量
int capacity = sum >> 1;
//dp[i][j]表示前i个石头放进容量为j的背包所能获取的最大重量
int dp[][] = new int[length + 1][capacity + 1];
for (int i = 1; i <= length; i++) {
for (int j = 1; j <= capacity; j++) {
//如果背包剩余容量能放下石头stones[i - 1]，取把石头stones[i - 1]放进
//背包和不放进背包的最大值
if (j >= stones[i - 1]) {
dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - stones[i - 1]] + stones[i - 1]);
} else {
//背包容量已经放不下石头了
dp[i][j] = dp[i - 1][j];
}
}
}
//sum - dp[length][capacity]是一部分，dp[length][capacity]是另一部分，上面
//capacity的取值是sum >> 1，往下取整，所以前面的肯定不小于后面的，不需要取绝对值
return (sum - dp[length][capacity]) - dp[length][capacity];
}
public int lastStoneWeightII(int[] stones) {
int length = stones.length;
int sum = 0;
for (int num : stones) {
sum += num;
}
//背包的容量
int capacity = sum >> 1;
int dp[] = new int[capacity + 1];
for (int i = 1; i <= length; i++) {
//这里要从大到小开始遍历
for (int j = capacity; j >= 1; j--) {
//如果背包剩余容量能放下石头stones[i - 1]，取把石头stones[i - 1]放进
//背包和不放进背包的最大值
if (j >= stones[i - 1]) {
dp[j] = Math.max(dp[j], dp[j - stones[i - 1]] + stones[i - 1]);
}
}
}
return (sum - dp[capacity]) - dp[capacity];
}
