用动态规划解决多米诺骨牌问题

问题描述:

有一种多米诺骨牌是平面的,其正面被分成上、下两个部分,每一部分的表面或者为空,或者被标上1至6个点。现在有一行多米诺骨牌排列在桌面上,如下图:


顶行(上行)骨牌的点数之和为6+1+1+1=9;底行(下行)骨牌的点数之和为1+5+3+2=11。顶行和底行的差值是2,这个差值是上、下两行点数之和的差的绝对值。每个多米诺骨牌都可以上下翻转倒置交换,即上部变为下部,下部变为上部。

现在的任务是,以最少的翻转次数,使得顶行和底行之间的差值最小。对于上面这个例子,我们只需要翻转最后一个骨牌,就可以使得顶行和底行的差值为0。所以这个例子的答案为1。

输入格式

第1行是一个整数n(1<=n<=1000),表示有n个多米诺骨牌。

接下来共有n行,每行包含两个整数a,b(0<=a,b<=6),之间用一个空格隔开,第i+1行的a,b分别表示第i个多米诺骨牌的上部和下部的点数(0表示空)。

输出格式
一行只有一个整数,表示最少需要的翻转次数,从而使得顶行和底行的差值最小。

输入样例
4

6 1

1 5

1 3

1 2

输出样例

1

解决思路1:

背包问题的变型

以骨牌顶行的和为背包,其最大容量为sum/2,(sum为所有骨牌顶行和底行之和),每个骨牌都有两种入包的选择,顶行的数或底行的数,产生的翻转分别为0和1,选择入包的方法,使其和最接近sum/2,而且其翻转次数最少。

DP[i][j]=min(DP[i-1][j-顶行的数],DP[i-1][j-底行的数],DP[i][j])

DP数组的初值都赋为最大值,因为每个骨牌在选择时,必须要求前面的骨牌已选择,类似于背包的“恰好装满”。

代码示例(c++):

#include <iostream>

#include <vector>

#include <fstream>

using namespace std;

int main()

{

// ifstream cin("data/domino8.in");

for(int n;cin>>n;)

{

int i,j;

vector<int> first(n+1),second(n+1);

int sum=0;

for(i=1;i<=n;i++)

{

cin>>first[i]>>second[i];

sum+=first[i]+second[i];

}

sum/=2;

vector<vector<int> > DP(n+1,vector<int>(sum+1,10000)); //二维数组,初值为最大值10000

DP[0][0]=0; //只有在和为0,没有骨牌时,翻转次数为0

for(i=1;i<=n;i++)

{

for(j=1;j<=sum;j++)

{

if(j>=first[i] && DP[i-1][j-first[i]]<DP[i][j]) DP[i][j]=DP[i-1][j-first[i]];

if(j>=second[i] && DP[i-1][j-second[i]]+1<DP[i][j]) DP[i][j]=DP[i-1][j-second[i]]+1;

}

}

for(j=sum;j>=1;j--)

if(DP[n][j]!=10000)

{

cout<<DP[n][j]<<endl;

break;

}

}

}

解决思路2

骨牌顶行的点数之和,与骨牌底行点数之和之差一开始是确定的,6+1+1+1-(1+5+3+2)=-2,每一个骨牌的翻转对差的影响分别为-10,8,4,2,这样枚举所有出现的差的情况,每种差都选择翻转次数最小达到的情况。

这种思路的优点在于压缩了状态,使影响结果的状态由两种变为一种。

 代码示例(c++):

#include <iostream>

#include <vector>

#include <fstream>

using namespace std;

int main()

{

// ifstream cin("data/domino8.in");

for(int n;cin>>n;)

{

vector<int> data(n);

int i,j;

int first,second;

int sum=0,dif=0;

for(i=0;i<n;i++)

{
cin>>first>>second;

data[i]=(second-first) * 2;

dif+=first-second; //差值之和

sum+=(first>=second?first-second:second-first);//可能的最大的差值

}

if(dif==0)

{

cout<<0<<endl;

continue;

}

vector<int> DP1(sum*2+1,10000),DP2(sum*2+1,10000); //整体移动sum位

for(j=0;j<=sum*2;j++) //初值为最大值

DP1[j]=10000;



DP1[dif+sum]=DP2[dif+sum]=0;

for(i=0;i<n;i++)

{

for(j=sum*2;j>=0;j--)

if(DP1[j]!=10000)

if(DP2[j+data[i]]>DP1[j]+1) DP2[j+data[i]]=DP1[j]+1;

DP1=DP2;

}

int min=10000,turn=10;

for(j=0;j<=sum*2;j++)

if(DP1[j]!=10000)

if(abs(j-sum)<min)

{

min=abs(j-sum);

turn=DP1[j];

}

else if(abs(j-sum)==min && turn<DP1[j])

turn=DP1[j];

cout<<turn<<endl;

}

}

解决思路3:

以最少的翻转次数,使得顶行和底行之间的差值最小

一个骨牌对翻转策略造成影响的是上下两数之差,把骨牌的放置状态由8个数字变为4个:5 -4 -2 -1,翻转时只需取该位数字的相反数就行了。

抽象为一个数学模型:给定一组整数,每个数可以翻转成其相反数,以最少的翻转次数,使这个序列的和的绝对值最小。

以树来表示,每个数都有两种出现方式:或正或负,这样就构成了一棵完全二叉树。设所有数都以正的情况出现的和为sum,则这个数列的和的范围为-sum到sum之间,为了使数组的下标正好对应其每一种和的状况,让每个数列和加上sum。

这种思路下,好像有更优的解法,没有理解,欢迎交流。