经典ACM算法合集经典ACM算法合集(13)

经典ACM算法合集经典ACM算法合集

是相应的价格，给出总价格不超过d的最小重量机器设计。

2、题目分析：
考虑到从每一处供应商购得每一种部件的重量和相应价格以及总价格的上限已给定，要设计最小重量机器方案计算最小重量，可用回溯法搜索排列树的算法进行求解。

3、算法设计：
a. 部件有n个，供应商有m个，分别用w[i][j]和c[i][j]存储从供应商j 处购得的部
件i的重量和相应价格，d为总价格的上限。
b. 用递归函数Knapsack(i,cs,ws)来实现回溯法搜索排列树（形式参数i表示递归深
度，n用来控制递归深度，形式参数cs和ws表示当前总价格和总重量，bestw表示当前
最优总重量）：
① 若cs>d，则为不可行解，剪去相应子树，返回到i-1层继续执行；
② 若ws>=bestw，则不是最优解，剪去相应子树，返回到i-1层继续执行；
③ 若i >n，则算法搜索到一个叶结点，用bestw对最优解进行记录，返回到
i-1层继续执行；
④ 采用for循环对部件i从m个不同的供应商购得的情况进行讨论(1≤j≤m）：
1> 调用递归函Knapsack(i+1,cs+c[i][j],ws+w[i][j])对部件i+1进行购买；
2> 当j>m时for循环结束；
⑤ 当i=1时，若已测试完所有购买方案，外层调用就全部结束；
c. 主函数调用一次Knapsack(1,0,0)即可完成整个回溯搜索过程，最终得到的bestw
即为所求最小总重量。

4、源程序：

#include<stdio.h>
#define MIN 1000
int n,m,d,cs,ws,bestw;
int w[100][100],c[100][100];

void Knapsack(int i,int cs,int ws)
{
int j;
if(cs>d)
return;
else if(ws>=bestw)
return;
else if(i>n)
{
bestw=ws;
return;
}
else
{
for(j=1;j<=m;j++) Knapsack(i+1,cs+c[i][j],ws+w[i][j]);
}
}

main()
{
int i,j;
scanf("%d%d%d",&n,&m,&d);
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
scanf("%d",&c[i][j]);
}
for(i=1;i<=n;i++)
{
for(j=1;j<=m;j++)
scanf("%d",&w[i][j]);
}
bestw=MIN;
Knapsack(1,0,0);
if(bestw==MIN)
printf("No Solution!");
else
printf("%d",bestw);
return 0;
}


5、算法分析：
递归函数Knapsack(i,cs,ws)遍历排列树的时间复杂度为O（n!）；主函数的双重for
循环的时间复杂度为O(mn)， 且主函数调用递归函数Knapsack(1,0,0)，故该算法的时
间复杂度为O（n!）。

实验十四 最小权顶点覆盖问题

1、问题描述：
? 给定一个赋权无向图G=(V,E)，每个顶点v∈V都有一个权值w(v)。如果U包含于V，且对于(u,v)∈E 有u∈U 且v∈V-U，则有v∈K.如
：U = {1}, 若有边（1，2）， 则有2属于K. 若有集合U包含于V使得U + K = V, 就称U 为图G 的一个顶点覆盖。G 的最小权顶点覆盖是指G 中所含顶点权之和最小的顶点覆盖。

2、题目分析：
考虑到每个顶点有在与不在顶点覆盖集中两种情况，并且每个顶点的权值已给定

搜索“diyifanwen.net”或“第一范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，第一范文网，提供最新人文社科经典ACM算法合集经典ACM算法合集(13)全文阅读和word下载服务。