递归【2】（组合回溯（生成括号）、子集回溯（背包问题））
括号对
（组合型回溯）
分解成子问题，每一次添加括号分两步：
if左括号小于n，加左括号，然后k(index+1),
if左括号大于有括号，加右括号，k(index+1),然后收尾括号单独考虑，到达最后一位的后一位就是跳出函数之时。
#include
#include
#include
#include
#include
using namespace std;
const int N=20;
int n;
char temp[20];
int l=0,r=0;
void k(int index)
{l=0;r=0;
if(index==2*n) {printf("%s
",temp);return;}
if(index==2*n-1) {temp[index]=')';k(index+1);}
else{
if(index==0){temp[index]='(';k(index+1);}
else{
//for(int i=0;i<index;i++)
//{ if(temp[i]=='(') l++;if(temp[i]==')') r++;}printf("三左%d%d%d%d--%s--",l,r,n,index,temp);
// {
// temp[index]='(';
// k(index+1);}
//for(int i=0;i<index;i++)
//{ if(temp[i]=='(') l++;if(temp[i]==')') r++;}printf("三右%d%d%d%d-%s-",l,r,n,index,temp);
// {
// temp[index]=')';
// k(index+1);}
//少了下面这个for循环，浪费大半天
for(int i=0;i<index;i++)
{ if(temp[i]=='(') l++;if(temp[i]==')') r++;}
//printf("一%d%d%d",l,r,n);
if(l<n)
{
temp[index]='(';
k(index+1);
}
for(int i=0;ir)
{
temp[index]=')';
k(index+1);
}
}
}
}
int main()
{scanf("%d",&n);k(0);
// char str[]="(())";
// printf("%d%d",str[0]=='(',1);//str[0]=="(");
}背包问题
又是子问题和恢复现场，照着模版套
选或不选
#include
#include
#include
#include
#include
using namespace std;
const int N=13;
int n=2,W=2;
int wi[N]={1,2},ci[N]={5,6};
int weight=0;
int value=0;
int ans=-1;
void b(int index)
{
if(index==n) {if (value>ans) ans=value;
// printf("!%d %d!",weight,value);
return;}
b(index+1); //这一行也不能少
if(weight+wi[index]<=W)
{
weight+=wi[index];
value+=ci[index];
b(index+1);
weight-=wi[index];
value-=ci[index];//恢复现场是必要的
}
}
int main()
{
scanf("%d %d",&n,&W);
for(int i=0;i<n;i++){scanf("%d",&wi[i]);}
for(int i=0;i<n;i++){scanf("%d",&ci[i]);}
b(0);printf("%d",ans);
}
