Subsets-BagProblem
今天问了Adhoc大神，才知道子集和还有DP算法，难怪之前一直过不了那道去重复解，排序的子集和问题，算法就是错的，DFS超时，于是搜到了背包一系列，这个不论是ACM，还是面试都是考察的重点，
DP的精髓，于是看到了著名的背包九讲，决定慢慢吭，另外还搜到了diaorui大牛的博客，今年刚去Google，做最优化，感觉背包
还限制在01背包和贪心的可以选部分比的背包。。。现在才知道有很多背包，而且最关键的是子集和问题居然还有DP算法。。。
于是乎打算再次回顾DP，主要在背包，另外还有搜索空间的一些变化总结下，主要是N行和N+1行的区别
先赋上这道题目代码：
bool dp[10000][10000];
class Solution
{
public:
vector<int> onesolution;
vector<vector<int> > allsolution;
vector<vector<int> > combinationSum2(vector<int> &num, int target)
{
allsolution.clear();
onesolution.clear();
sort(num.begin(),num.end());
/*
for(int i=0;i<=num.size()-1;i++)
{
for(int j=0;j<=target;j++)
dp[i][j]=false;
}*/
KnackBag(num,target);
dfs2(num.size(),target,num);
vector<vector<int> > uniquesolution;
//if(allsolution.size()<=0)
// return uniquesolution;
//sort(allsolution[0].begin(),allsolution[0].end());
//uniquesolution.push_back(allsolution[0]);
//sort(uniquesolution[0].begin(),uniquesolution[0].end());
for(int i=0;i<=(int)allsolution.size()-1;i++)
{
/*
if(allsolution[i]!=allsolution[i-1])
{
//sort(allsolution[i].begin(),allsolution[i].end());
uniquesolution.push_back(allsolution[i]);
sort(uniquesolution.back().begin(),uniquesolution.back().end());
}*/
sort(allsolution[i].begin(),allsolution[i].end());
bool isunique=true;
for(int j=0;j<(int)uniquesolution.size();j++)
{
if(allsolution[i]==uniquesolution[j])
{
isunique=false;
break;
}
}
if(isunique)
uniquesolution.push_back(allsolution[i]);
}
return uniquesolution;
}
void KnackBag(vector<int>& num, int target)
{
int N=num.size();
for(int i=0;i<=N;i++)
{
dp[i][0]=true;
}
for(int j=1;j<=target;j++)
dp[0][j]=false;
for(int i=1;i<=N;i++)
{
for(int j=1;j<num[i-1];j++)
dp[i][j]=dp[i-1][j];
for(int j=num[i-1];j<=target;j++)
dp[i][j]=dp[i-1][j] || dp[i-1][j-num[i-1]];
}
}
void dfs(int i, int j,vector<int>& num)
{
if(i>0)
{
if(i>=1 && j>=0 && dp[i][j]==false)
return;
else
{
dfs(i-1,j,num);
if(j>=num[i-1])
{
onesolution.push_back(num[i-1]);
dfs(i-1,j-num[i-1],num);
onesolution.pop_back();
}
}
}
else if(i==0)
allsolution.push_back(onesolution);
}
void dfs2(int i,int j,vector<int>& num)
{
if(i>=0 && j>=0 && dp[i][j]==false) return;
else
{
if(i==0)
allsolution.push_back(onesolution);
else
{
dfs2(i-1,j,num);
if(j>=num[i-1])
{
onesolution.push_back(num[i-1]);
dfs2(i-1,j-num[i-1],num);
onesolution.pop_back();
}
}
}
}
};
int main()
{
//write;
Solution S;
int a[]={13,23,25,11,7,26,14,11,27,27,26,12,8,20,22,34,27,17,5,26,31,11,16,27,13,20,29,18,7,14,13,15,25,25,21,27,16,22,33,8,15,25,16,18,10,25,9,24,7,32,15,26,30,19};
vector<int> num(&a[0],&a[sizeof(a)/sizeof(int)]);
int target=25;
time_t start=clock();
vector<vector<int> > solution=S.combinationSum2(num,target);
time_t end=clock();
cout<<end-start<<endl;
for(int i=0;i<solution.size();i++)
{
for(int j=0;j<solution[i].size();j++)
cout<<solution[i][j]<<" ";
cout<<endl;
}
return 0;
}
里面主要是又犯了DP的递推公式的问题，也即DP搜索空间本来应该N+1行又写成了N行了，还有回溯求解这块有点生疏了，记得当时矩阵链，LCS等回溯的时候好像也不是很顺。
于是又重新看了一下DP算法的几个问题，其实应该都有一个i=0的 不存在的一个解空间行，这样每次回溯到这里就是构造一个解的过程结束，并且尤其要注意这一行的初值的情况
例如LCS MinEditDis 01Bag等等，其实都是一类，从i=0->N, 开始构造，和矩阵链不同，矩阵链是中间断开作为一次选择，因此dp[i][j]长度应该从短到长递推求解状态图状态，矩阵链的初始状态，或者说
递归出口是dp[i][j] i=j的情况，不需要额外找一个i=0的空行。
回到01背包，dp[i][j], i=0->N, j=0->target, 那么初始值为i=0, 也即一个物品都不选，背包>=0 最优值都为0， 因为没有物品可选
所以递推伪代码：
for i=1->N
for j=0->a[i-1]-1
dp[i][j]=dp[i-1][j]
for j=a[i-1]->target
dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i-1]+v[i-1]];
把他运用到子集和问题，需要修改下状态图的定义，原始的是dp[i][j]表示 选前i个背包，包重j时，最大价值(包未必装满，如果要求装满只需要改个初值条件，源自背包九讲)，
子集和问题，v[i]=w[i], 不再侧重于最后的value，因为最优value都是 target，而是把所有解求出，也即一个01向量，所以dp[i][j]这里表示 用前i个背包，和j的子集是否存在，bool的状态空间，
初值条件特别当心，dp[0][j]=0, j=1..target, 表示j不空，不选包不存在解，这是显然的，dp[0][0]=1,这个要特别注意，不选物品，包重0， 存在一个空集解，子集和解也可以是空集，只是题目说了和都是正整数罢了，
所以这也是自己之前一再强调的对于初始条件，一定要分析清楚，不要盲目赋0，
因此递推伪代码(基于完全背包的子集和问题)：
for i=1->N
for j=0->target
dp[i][j]=false;
for k=0;k*a[i-1]<=j;k++
dp[i][j]+=dp[i-1][j-k*num[i-1]]
这里面受到了adhoc的启发，本来是或运算，现在改成等价于bool值的加法，其实bool只有二值，多个或只要一个true就是true，和加法一样的。但是一定要记得dp[i][j]初始为false，
要么一开始memset，要么每次两重循环一进来就赋false
有了这个之后就是回溯求解这块要特别注意，如果dp[i][j]=false, 那么就当前无解了，直接返回，否则看是否递归到底，即遍历完所有的数了，其实说白了01背包是多重背包的特列，只是一开始学的时候
写成单独的两项，其实也可以写成完全背包的式子，k=0 1两种情况
void dfs2(int i,int j,vector<int>& num)
{
if(i>=0 && j>=0 && dp[i][j]==false) return;
else
{
if(i==0)
allsolution.push_back(onesolution);
else
{
dfs2(i-1,j,num);
if(j>=num[i-1])
{
onesolution.push_back(num[i-1]);
dfs2(i-1,j-num[i-1],num);
onesolution.pop_back();
}
}
}
}
赋上diaorui大牛的博客 http://diaorui.net/archives/567
以及著名的OIer Cui牛的 背包九讲 http://diaorui.net/archives/567
北邮某同学帖子，比较认同为啥SSP问题不讲DP解法的观点 http://bbs.byr.cn/#!article/ACM_ICPC/43221
这里再对DP状态空间做个总结，像这种每次做的选择划分成n-1规模的一个子问题，一般都要构建一个不存在的N=0的解空间行，构造解回溯到这里表示结束，也是初始递推状态。这也是受cuitianyi大牛的影响，
虽然他没有将背包解法推广到其他问题，这个推广是看到北邮一个同学说的，我也觉得纳闷这种DP解法教材都不讲，后来问沈老师，他好像也不是很了解。
Adhoc大神确实太强，用无与伦比来形容他的DS Alg能力毫不为过，只可惜没有代表复旦ACM比赛，打Final问题不大。这也无可厚非，大学才开始接触编程，算法，数据结构的人怎么和 从小学就开始
编程，Alg DS的人比呢，就和音乐人一样，怎么和4岁开始学钢琴的人比，周董的钢琴已经不能再熟了，所以小孩从小的培养很重要，尤其是明确知道自己喜欢什么，以后走那条路的时候。
或运算本质就是bool值加法，异或本质似乎是bool值带进位，且进位丢弃的加法。
01背包 时复 O(NC) 著名的伪多项式算法，空复O(NC), int类型状态空间，cui牛博客说可以空复降到O(C)，求最优值，一次循环构造唯一解
01选法子集和 时复 同上，空复O(NC), bool 类型状态空间，无最优值，有多个解集，递归类dfs算法构造解集，参数加上dp[][], dp[][]=false return
完全背包 时复O(NC*max(C/a[i])), 复杂度较高，空复O(NC), int类型状态空间
完全选法子集和，时复同上，空复O(NC)， bool 类型状态空间，无最优值，有多个解集，递归类dfs算法构造解集，参数加上dp[][], dp[][]=false return