前言：背包问题原理详见背包问题原理及leetcode实战（上）；
本文从LeetCode实战出发，讲解背包问题在具体算法题中的应用、变形，本质上的思路没有太大变化，不同的是每道题要处理的细节。
注：题目设置了超链接，可以点击进入LeetCode查看更多的题解。
LeetCode.494 目标和
问题描述：给定一个非负整数数组，{a1, a2, ..., an}, 和一个目标数S。现在你有两个符号+ 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S的所有添加符号的方法数。注意，数组长度不超过20，数组各元素之和不超过1000。
思考：这个问题类似背包问题，遍历数组的话，对每个数字可以选择加法或减法。设F[i][j]表示前i+1个数字的和为j的方案数，可以看出，如果i=0，也就是只考虑第一个数，那么只有当j=nums[0]和j=-nums[0]的时候方案数为1（如果nums[0]==0，那么F[0][0]=2），其余方案数均为0。
考虑第i个数字的处理，只和F[i-1][j]有关，可以写出状态转移方程：F[i][j]=F[i-1][j-nums[i]]+F[i-1][j+nums[i]]。
代码实现：我们注意到，前面的状态转移方程存在一点问题，就是j-nums[i]有可能是负数，包括初始化的j=-nums[0]也有可能是负数，而c++中的数组下标不允许有负数出现。对于这一点，结合题目中给出的“数组各元素之和不超过1000”，我们可以把F[i][j]这个数组的[j]这个维度向后推1000个位置。
所以初始化应该这样写：
F[0][1000+nums[0]]=1;
F[0][1000-nums[0]]+=1; // 注意这里的+=，是考虑了nums[0]=0这种情况，也可以写成if语句
背包问题的核心部分，也就是两层遍历的地方可以这样写：
for (int i = 1; i < nums.size(); i++)
{
for(int j=0;j<2000;j++)
{
if(j+nums[i]>2000)
F[i][j]=F[i-1][j-nums[i]];
else if(j-nums[i]<0)
F[i][j]=F[i-1][j+nums[i]];
else
F[i][j]=F[i-1][j-nums[i]]+F[i-1][j+nums[i]];
}
}
最后，加上一些特殊情况的判断，就完成了，所有代码如下：
int findTargetSumWays(vector<int>& nums, int S) {
vector<vector<int> > F(nums.size(),vector<int>(2002,0));
// 特殊情况判断
if(nums.size()==1)
if(S==nums[0]||S==-nums[0])
return 1;
else
return 0;
if(nums.size()==0)
return 0;
if(S>1000)
return 0;
// 初始化
F[0][1000+nums[0]]=1;
F[0][1000-nums[0]]+=1;
// 背包问题核心
for (int i = 1; i < nums.size(); i++)
{
for(int j=0;j<2000;j++)
{
if(j+nums[i]>2000)
F[i][j]=F[i-1][j-nums[i]];
else if(j-nums[i]<0)
F[i][j]=F[i-1][j+nums[i]];
else
F[i][j]=F[i-1][j-nums[i]]+F[i-1][j+nums[i]];
}
}
return F[nums.size()-1][1000+S]; // 注意返回的也是1000+S
}
优化思路：对于此问题的优化，由于状态转移方程中既存在j+nums[i]，又存在j-nums[i]，相当于对于当前点j的计算用到了左右两侧的数据，这不好用上一篇文章提到的逆序或正序遍历来解决。但是，我们可以建立一个数组F[2][j]来代替之前的F[N][j]，这样也会使得空间复杂度由O(N*sum)降为O(sum)。
面试题08.11 硬币
问题描述：给定数量不限的硬币，币值为25分、10分、5分和1分，编写代码计算n分有几种表示法。结果对1000000007取余，0 <= n (总金额) <= 1000000。
思考：由于存在四种面值的硬币，每种硬币的数量是没有做限制的，可以无限取，所以这个问题属于完全背包问题。由于n的值可能会特别大，为了节省时间和空间的复杂度，这里一定要采用一维数组（二维数组无法通过）。结合前面分析过的完全背包问题的解法，首先是一层遍历，遍历每个硬币，设第i轮循环的F[j]表示使用当前i-1种硬币能凑成j分的方案数。状态转移方程为F[j]=F[j]+F[j-nums[i]]。
代码实现：套用完全背包问题的模板即可，不需要特殊情况判断（可以试一下特殊情况可不可以通过），只需要初始化+状态转移方程。完整代码如下：
int waysToChange(int n) {
int a[]={1,5,10,25};
vector<int> num(a,a+4);
vector<int> F(n+1,0);
for(int j=0;j<n+1;j++)
F[j]=1;
for(int i=1;i<4;i++)
for(int j=num[i];j<=n;j++)
F[j]=(F[j]+F[j-num[i]])%1000000007;
return F[n];
}
LeetCode.416 分割等和子集
问题描述：给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
思考：首先容易想到的是，数组的和应该是一个偶数，我们的目标是寻找到一个数组的子集，使得这个子集中的数字的和为整个数组和的一半，假设这个目标数字（子集的数字和）为sum。这是一个0-1背包问题，因为数组中的数字面临两个选择：属于和不属于分割后的子集。假设F[j]表示仅考虑前i个数字，组成的子集的和能不能为j。F[j]有两个取值，0或1。状态转移方程容易写出：F[j]=max(F[j],F[j-nums[i]]。这里选择max()函数的原因是，只要里面两个值有一个为1（子集和可以为j），那么F[j]就是1。
代码实现：首先要计算子集的目标和，也就是sum的值。
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if(sum%2==1)
return false;
sum=sum/2;
后面根据状态转移方程，写出两层遍历的代码。
vector<int> F(sum+1,0);
F[nums[0]]=1;
for (int i = 1; i < nums.size(); i++)
{
for(int j=sum;j>=nums[i];j--)
{
if(j==nums[i]) // 这一步经常漏掉
F[j]=1;
else
F[j]=max(F[j],F[j-nums[i]]);
}
}
完整代码如下：
bool canPartition(vector<int>& nums) {
if(nums.size()<2)
return false;
int sum=0;
for(int i=0;i<nums.size();i++)
{
sum+=nums[i];
}
if(sum%2==1)
return false;
sum=sum/2;
vector<int> F(sum+1,0);
F[nums[0]]=1;
for (int i = 1; i < nums.size(); i++)
{
for(int j=sum;j>=nums[i];j--)
{
if(j==nums[i])
F[j]=1;
else
F[j]=max(F[j],F[j-nums[i]]);
}
}
return F[sum];
}
背包问题的变形有很多，但思路比较统一，也就是确定是哪种背包问题--初始化条件--写出状态转移方程，接着套用模板即可。
