《三国杀》张昌蒲严教算法
玩《三国杀》的时候想出了这个问题。 严教：出牌阶段限一次，你可以选择一名其他角色。从牌堆顶亮出四张牌，该角色将这些牌分成点数之和相等的两组，你与其各获得其中一组，然后将剩余未分组的牌置入弃牌堆。若未分组的牌超过一张，你本回合手牌上限-1。
张昌蒲可以亮出牌堆顶的n张牌（初始n=4），经典天平问题。每张牌有三种策略：放左边，放右边，弃置。那么我们编写一个程序，将所有牌的点数作为输入，输出所有的可行方案。
算法一：直接暴力深搜，最后使用13进制哈希（因为卡牌的点数A到K，分别对应0到12，注意不是1到13）去除重复方案。复杂度O(3^n)
优化：将点数一样的牌一起处理，可以减少一部分重复。
可行性剪枝：计算卡牌点数的后缀和。如果将所有剩余卡牌都放在天平轻的一侧仍然轻，那么此状态无解，直接return;
#include<bits/stdc++.h>
using namespace std;
int a[12],numa[12],n,s,h[12],l[12],r[12],num,num2,numans,w;
bool b[1000005];
char c;
struct answer
{
int num,num2,l[12],r[12];
};
answer ans[10005];
bool mycmp(answer x1,answer x2)
{return x1.num+x1.num2>x2.num+x2.num2;}
void f(int t)
{
if(t>n)
{
if(!w&&num)
{
int hash=l[1]-1,hash2=r[1]-1;
for(int i=2;i<=num;i++)
hash=(hash*13+l[i]-1)%999983;
for(int i=2;i<=num2;i++)
hash2=(hash2*13+r[i]-1)%999983;
if(!b[hash]||!b[hash2])//13进制哈希查重
{
b[hash]=b[hash2]=1;
numans++;
ans[numans].num=num,ans[numans].num2=num2;
for(int i=1;i<=num;i++)
ans[numans].l[i]=l[i];
for(int i=1;i<=num2;i++)
ans[numans].r[i]=r[i];
}
}
return;
}
if(abs(w)<=h[t])//可行性剪枝
{
for(int i=1;i<=numa[t];i++)//全放左侧
l[++num]=a[t];
w+=a[t]*numa[t];
f(t+numa[t]);
for(int i=1;i<=numa[t];i++)//逐个拿下，再放入右侧
{
num--;
w-=a[t];
f(t+numa[t]);
r[++num2]=a[t];
w-=a[t];
f(t+numa[t]);
}
num2-=numa[t];
w+=a[t]*numa[t];//回溯
}
}
int main()
{
while(scanf("%c",&c))
{
if(c==' ')
{
a[++n]=s;
s=0;
}
else if(c=='\n')
{
a[++n]=s;
break;
}
else s=s*10+c-48;
}
sort(a+1,a+n+1);
for(int i=n;i;i--)//后缀和
h[i]=h[i+1]+a[i];
for(int i=1;i<=n;i+=numa[i])
{
numa[i]=1;
for(int j=i+1;a[i]==a[j];j++)
numa[i]++;
}
f(1);
sort(ans+1,ans+numans+1,mycmp);
for(int i=1;i<=numans;i++)
{
printf("方案%d：",i);
for(int j=1;j<ans[i].num;j++)
printf("%d+",ans[i].l[j]);
printf("%d=",ans[i].l[ans[i].num]);
for(int j=1;j<ans[i].num2;j++)
printf("%d+",ans[i].r[j]);
printf("%d\n",ans[i].r[ans[i].num2]);
}
return 0;
}
算法二：使用对称性剪枝，保证在搜索时就能去除重复，故删除哈希。镜像重复的方案（手性）仅保留将第一张不对称卡牌放在左侧多的情况。
#include<bits/stdc++.h>
using namespace std;
int a[12],numa[12],n,s,h[12],l[12],r[12],num,num2,numans,w;
char c;
struct answer
{
int num,num2,l[12],r[12];
};
answer ans[10005];
bool mycmp(answer x1,answer x2)
{return x1.num+x1.num2>x2.num+x2.num2;}
void f(int t,bool fl)
{
if(t>n)
{
if(!w&&num)
{
numans++;
ans[numans].num=num,ans[numans].num2=num2;
for(int i=1;i<=num;i++)
ans[numans].l[i]=l[i];
for(int i=1;i<=num2;i++)
ans[numans].r[i]=r[i];
}
return;
}
if(abs(w)<=h[t])//可行性剪枝
{
for(int i=1;i<=numa[t];i++)//全放左侧
l[++num]=a[t];
w+=a[t]*numa[t];
f(t+numa[t],1);
//对称性剪枝，规定"打破对称的"第一张牌必须放左侧
if(fl)//无对称性要求
{
for(int i=1;i<=numa[t];i++)//逐个拿下，再放入右侧
{
num--;
w-=a[t];
f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
f(t+numa[t],1);
}
num2-=numa[t];
w+=a[t]*numa[t];//回溯
}
else//有对称性要求
{
if(num&1)//奇数
{
for(int i=1;i<=numa[t]>>1;i++)//逐个拿下，再放入右侧
{
num--;
w-=a[t];
f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
f(t+numa[t],1);
}
num--;
w-=a[t];
f(t+numa[t],0);
}
else
{
for(int i=1;i<=(numa[t]-1)>>1;i++)//逐个拿下，再放入右侧
{
num--;
w-=a[t];
f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
f(t+numa[t],1);
}
num--;
w-=a[t];
f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
f(t+numa[t],0);
}
}
}
}
int main()
{
while(scanf("%c",&c))
{
if(c==' ')
{
a[++n]=s;
s=0;
}
else if(c=='\n')
{
a[++n]=s;
break;
}
else s=s*10+c-48;
}
sort(a+1,a+n+1);
for(int i=n;i;i--)//后缀和
h[i]=h[i+1]+a[i];
for(int i=1;i<=n;i+=numa[i])
{
numa[i]=1;
for(int j=i+1;a[i]==a[j];j++)
numa[i]++;
}
f(1,0);
sort(ans+1,ans+numans+1,mycmp);
for(int i=1;i<=numans;i++)
{
printf("方案%d：",i);
for(int j=1;j<ans[i].num;j++)
printf("%d+",ans[i].l[j]);
printf("%d=",ans[i].l[ans[i].num]);
for(int j=1;j<ans[i].num2;j++)
printf("%d+",ans[i].r[j]);
printf("%d\n",ans[i].r[ans[i].num2]);
}
return 0;
}
算法三：使用记忆化搜索，复杂度降低到O(min(3^n,n*S))。S为卡牌点数和范围，S<=13n，显然复杂度达不到上界。
为w设置初始偏移量65（为了避免数组下标负数）。设状态dp[n][w]表示在当前状态下继续搜索下去是否有解（状态里没有fl，因为fl对是否有解无影响）。将f函数从void改为bool，传递当前状态的dp值。状态转移方程：dp[n][w]=max(dp[n+numa[n]][所有可能到达的状态w])
有了dp[n][w]的记录之后，所有重叠子问题最多计算一次，第二次遇到“此路不通”的情况会直接“掉头”，而遇到“有路”的情况只会在“正确的路上”行走，免去搜索直奔答案，不会走“岔路”。就像有了雅努斯（门径之泰坦）的指引一样顺利。
对于这类问题，我一般用记忆化搜索完成DP，理由：1.一般的DP需要用循环，这样会循环到很多不可能到达的状态，白白浪费时间。而记搜搜过的所有状态都是能到达的状态。2.这个问题需要输出答案，而且是多个答案，一般的DP写法很难存储多个答案，要么需要用邻接表建图保存答案，要么就要做完DP之后再次根据DP值深搜出答案，非常繁琐。虽然深搜的常数比较大。
#include<bits/stdc++.h>
using namespace std;
int a[12],numa[12],n,s,h[12],l[12],r[12],num,num2,numans,w=65;
char c;
bool dp[12][135],vis[12][135];
struct answer
{
int num,num2,l[12],r[12];
};
answer ans[10005];
bool mycmp(answer x1,answer x2)
{return x1.num+x1.num2>x2.num+x2.num2;}
bool f(int t,bool fl)
{
if(t>n)
{
if(w!=65||!num) return 0;
ans[++numans].num=num;
ans[numans].num2=num2;
for(int i=1;i<=num;i++)
ans[numans].l[i]=l[i];
for(int i=1;i<=num2;i++)
ans[numans].r[i]=r[i];
return 1;
}
if(abs(w-65)>h[t]||(vis[t][w]&&!dp[t][w]))
return 0;//可行性剪枝
vis[t][w]=1;
for(int i=1;i<=numa[t];i++)//全放左侧
l[++num]=a[t];
w+=a[t]*numa[t];
bool flag=0;
flag|=f(t+numa[t],1);
//对称性剪枝，规定"打破对称的"第一张牌必须放左侧
if(fl)//无对称性要求
{
for(int i=1;i<=numa[t];i++)//逐个拿下，再放入右侧
{
num--;
w-=a[t];
flag|=f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
flag|=f(t+numa[t],1);
}
num2-=numa[t];
w+=a[t]*numa[t];//回溯
}
else//有对称性要求
{
if(num&1)//奇数
{
for(int i=1;i<=numa[t]>>1;i++)//逐个拿下，再放入右侧
{
num--;
w-=a[t];
flag|=f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
flag|=f(t+numa[t],1);
}
num--;
w-=a[t];
flag|=f(t+numa[t],0);
}
else
{
for(int i=1;i<=(numa[t]-1)>>1;i++)//逐个拿下，再放入右侧
{
num--;
w-=a[t];
flag|=f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
flag|=f(t+numa[t],1);
}
num--;
w-=a[t];
flag|=f(t+numa[t],1);
r[++num2]=a[t];
w-=a[t];
flag|=f(t+numa[t],0);
}
}
return dp[n][w]=flag;
}
int main()
{
while(scanf("%c",&c))
{
if(c==' ')
{
a[++n]=s;
s=0;
}
else if(c=='\n')
{
a[++n]=s;
break;
}
else s=s*10+c-48;
}
sort(a+1,a+n+1);
for(int i=n;i;i--)//后缀和
h[i]=h[i+1]+a[i];
for(int i=1;i<=n;i+=numa[i])
{
numa[i]=1;
for(int j=i+1;a[i]==a[j];j++)
numa[i]++;
}
f(1,0);
sort(ans+1,ans+numans+1,mycmp);
for(int i=1;i<=numans;i++)
{
printf("方案%d：",i);
for(int j=1;j<ans[i].num;j++)
printf("%d+",ans[i].l[j]);
printf("%d=",ans[i].l[ans[i].num]);
for(int j=1;j<ans[i].num2;j++)
printf("%d+",ans[i].r[j]);
printf("%d\n",ans[i].r[ans[i].num2]);
}
return 0;
}
算法四：考虑到这个问题只有一个起点（w=0）和一个终点（也是w=0），故从两端开始搜索，在中间汇合。大大降低时间复杂度。但我认为对这道题来说使用这个策略是有些多此一举的，甚至不一定比得过算法三。两端搜索的策略适合指数爆炸式复杂度的问题，适合越往深处搜索，结点数量便指数爆炸式增长的问题。而这个问题当n过半之后，范围S由于可行性剪枝反而缩小了。呈现“两头尖，中间大”的形态。两端搜索的目的就是为了达成“两头尖，中间大”的形态并在中间汇合，这个目的已经达成了，再用两端搜索就多此一举了。而且两端搜索还会增加代码量，需要两半对接答案，也更繁琐。
策略游戏嘛，算法打击！