基本的「将原问题抽象为 01 背包问题」的分析在 上一讲 讲过啦 ~
本节要解决的问题是:如何将「间接求解」的方式转为「直接求解」,并学习为什么能这么做,此类做法是否有共性 ...
我们先来回顾一下 上一讲 使用的「状态定义」和「转移方程」。
状态定义:
1. dp[i-1][j] (不选第 i 件物品,选择的数字总和恰好为 j ) 为 true;
2. dp[i-1][j-nums[i]] (选第 i 件物品,选择的数字总和恰好为 j ) 为 true;
大白话时间: 求解当前物品当前容量的状态下的结果其实就是把当前容量减去物品大小,剩余的空间为p,然后问题就转变为了在考虑前一个物品,对应容量为p的情况下能否满足条件,这里就是能否物品最大价值刚好等于背包最大容量,如果能返回true,不能返回false;
class Solution {
public:
bool canPartition(vector<int>& nums)
{
int size = nums.size();
if (size < 2) return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;//总和为奇数
int target = sum / 2;
// dp[i][j] 代表考虑前 i 件物品,能否凑出价值「恰好」为 j 的方案
vector<vector<bool>> dp(size+1,vector<bool>(target + 1, false));
//最小子问题
dp[0][0]=true;//当你什么物品都没有,并且背包容量为0时,肯定满足条件
//枚举每一个物品
for (int i = 1; i <= size; i++)
{
int t = nums[i-1];//临时保存当前物品的价值
for (int j = 0; j <= target; j++)
{
//不选择当前物品放入背包
bool unsel = dp[i - 1][j];
//选择当前物品放入背包
bool sel = j >= t ? dp[i - 1][j - t] : false;
dp[i][j] = unsel || sel;
}
}
return dp[size][target];
}
};
class Solution {
public:
bool canPartition(vector<int>& nums)
{
int size = nums.size();
if (size < 2) return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;//总和为奇数
int target = sum / 2;
// dp[i][j] 代表考虑前 i 件物品,能否凑出价值「恰好」为 j 的方案
vector<vector<bool>> dp(2,vector<bool>(target + 1, false));
//最小子问题
dp[0][0]=true;//当你什么物品都没有,并且背包容量为0时,肯定满足条件
//枚举每一个物品
for (int i = 1; i <= size; i++)
{
int t = nums[i-1];//临时保存当前物品的价值
for (int j = 0; j <= target; j++)
{
//不选择当前物品放入背包
bool unsel = dp[(i - 1)&1][j];
//选择当前物品放入背包
bool sel = j >= t ? dp[(i - 1)&1][j - t] : false;
dp[i&1][j] = unsel || sel;
}
}
return dp[size&1][target];
}
};
class Solution {
public:
bool canPartition(vector<int>& nums)
{
int size = nums.size();
if (size < 2) return false;
int sum = accumulate(nums.begin(), nums.end(), 0);
if (sum & 1) return false;//总和为奇数
int target = sum / 2;
// 取消「物品维度」
vector<bool> dp(target + 1);
//最小子问题
dp[0]=true;//当你什么物品都没有,并且背包容量为0时,肯定满足条件
//枚举每一个物品
for (int i = 1; i <= size; i++)
{
int t = nums[i-1];//临时保存当前物品的价值
for (int j = target; j>=0; j--)//防止数据覆盖,从尾端到前段覆盖
{
//不选择当前物品放入背包
bool unsel = dp[j];
//选择当前物品放入背包
bool sel = j >= t ? dp[j - t] : false;
dp[j] = unsel || sel;
}
}
return dp[target];
}
};