算法设计与分析实验四回溯法+子集树+最大团+0-1背包问题求解

系统管理员 2022-07-15 05:22 143阅读 0赞

<table> 
 <tbody> 
 <tr> 
 <td align="left"> 1.题目描述：（类0-1背包问题） 有一群小鸭子要漂洋过海，但是这n只小鸭子都不会游泳，而且他们只有两艘载重量为c1和c2的船，其中小鸭子i的重量为wi，小鸭子们都很团结，他们要么一起过海，要么一个都不过，试判断这n只小鸭子能否全部过海，该如何分配他们的位置。 输入：n,c1,c2三个整数表示鸭子的重量和两艘船的载重量； Wi(i=1,…,n)共n个整数表示每只小鸭子的重量。 输出：鸭子们能否漂洋过海，若能，则输出两只船上分别要放哪几只小鸭子。 &nbsp; 采用回溯法子集树来实现： &nbsp; 代码实现： <pre><code>#include &lt;iostream&gt;
#include &lt;cstdio&gt;
#include &lt;cstring&gt;

using namespace std;

int n,w[100],c1,c2;
int r;//表示未装入船1中的重量
int bestw;//表示最多放入船中的重量
int x[100],bestx[100];
int cw;//当前载重量

void bt(int t)
{
    if(t&gt;n)
    {
        if(cw&gt;bestw)
        {
            bestw=cw;
            for(int i=1; i&lt;=n; i++)
            {
                bestx[i]=x[i];
            }
        }
        return;
    }
    r-=w[t];
    if(cw+w[t]&lt;=c1)
    {
        x[t]=1;
        cw+=w[t];
        bt(t+1);
        cw-=w[t];
    }
    if(cw+r&gt;bestw)
    {
        x[t]=0;
        bt(t+1);
    }
    r+=w[t];
}

int main()
{
    while(scanf("%d",&amp;n)!=EOF)
    {
        scanf("%d%d",&amp;c1,&amp;c2);
        r=0;
        for(int i=1; i&lt;=n; i++)
        {
            scanf("%d",&amp;w[i]);
            r+=w[i];
        }
        cw=0;
        bestw=0;
        memset(x,0,sizeof(x));
        memset(bestx,0,sizeof(bestx));
        bt(1);
        int sum=0,sum1=0;
        int sumweight=0;
        for(int i=0; i&lt;=n; i++)
        {
            if(bestx[i])
            {
                sum++;
            }
            else
            {
                sumweight+=w[i];
            }
        }
        if(sumweight&lt;=c2)
        {
            cout&lt;&lt;"一共有"&lt;&lt;sum&lt;&lt;"个小鸭子装入了船1中,小鸭子编号分别是: "&lt;&lt;endl;
            for(int i=1; i&lt;=n; i++)
            {
                if(bestx[i])
                {
                    cout&lt;&lt;i&lt;&lt;endl;
                }
            }
            cout&lt;&lt;"一共有"&lt;&lt;n-sum&lt;&lt;"个小鸭子装入了船2中,小鸭子编号分别是："&lt;&lt;endl;
            for(int i=1;i&lt;=n;i++)
            {
                if(bestx[i]==0)
                {
                    cout&lt;&lt;i&lt;&lt;endl;
                }
            }
        }
        else
        {
            cout&lt;&lt;"不能把所有的货物都装入两艘船中！"&lt;&lt;endl;
        }

}
    return 0;
}
/*
3 50 50
10 40 40

3 50 50
20 40 40

*/
</code></pre> 2.问题描述：最大团问题，用子集树实现 已知n个城市之间花了十年一共修好的m条路，路人甲想生活在一个交通极其便利的环境下，所以他想知道是否存在这样的几个城市，他们可以彼此直接到达，请帮助路人甲找到满足他所提出条件的最多的城市，并输出城市的个数和城市。 输入：n，m两个整数表示n个城市之间有m条边 Xi&nbsp; Yi(i=1,…,m)表示城市之间有路 输出：最大团中包含点的数目和点分别是什么。 &nbsp; 代码实现： <pre><code>#include &lt;iostream&gt;
#include &lt;cstdio&gt;
#include &lt;cstring&gt;

using namespace std;

int mapp[100][100];
int m,n;//n个顶点，m条边
int cn;//已经加入团的顶点数
int bestn;//最大团中所包含的顶点的个数
int bestx[100];
int x[100];

void bt(int t)
{
    if(t&gt;n)
    {
        if(cn&gt;bestn)
        {
            bestn=cn;
            for(int i=1; i&lt;=n; i++)
            {
                bestx[i]=x[i];
            }
        }
        return;
    }

int OK=1;

for(int j=1; j&lt;t; j++)
    {
        if(x[j]&amp;&amp;mapp[j][t]==0)
        {
            OK=0;
            break;
        }
    }

if(OK)//如果能加入团中
    {
        x[t]=1;
        cn++;
        bt(t+1);
        x[t]=0;
        cn--;
    }
    if(cn+n-t&gt;bestn)
    {
        x[t]=0;
        bt(t+1);
    }
}

int main()
{
    int u,v;
    while(scanf("%d%d",&amp;n,&amp;m)!=EOF)
    {
        memset(x,0,sizeof(x));
        memset(bestx,0,sizeof(bestx));
        memset(mapp,0,sizeof(mapp));
        for(int i=1; i&lt;=m; i++)
        {
            scanf("%d%d",&amp;u,&amp;v);
            mapp[u][v]=1;
            mapp[v][u]=1;
        }

cn=0;
        bestn=0;

bt(1);
        int sum=0;
        for(int i=1; i&lt;=n; i++)
        {
            if(bestx[i])
            {
                sum++;
            }
        }
        if(sum&gt;0)
        {
            cout&lt;&lt;"最大团中所含顶点个数为："&lt;&lt;sum&lt;&lt;"个,加入团的顶点编号分别为："&lt;&lt;endl;
            for(int i=1; i&lt;=n; i++)
            {
                if(bestx[i])
                {
                    cout&lt;&lt;i&lt;&lt;endl;
                }
            }
        }
        else
        {
            cout&lt;&lt;"没有任何结点可以加入团中"&lt;&lt;endl;
        }
    }
    return 0;
}
/*
5 7
1 2
1 3
1 4
2 3
2 4
3 4
4 5

4 4
1 2
2 3
1 3
1 4
*/

</code></pre> </td> 
 </tr> 
 </tbody> 
</table>