精华内容
下载资源
问答
  • 2、求解最小机器重量设计问题1 问题描述:设某一机器由n个部件组成,部件编号为1~n,每一种 部件都可以从m个不同的供应商处购得,供应商编号哦1~m。设 wij是从供应商j处购得的部件i的重量,cij 是相应的价格。试设计 ...
  • 利用C++实现最小重量机器设计问题,通过input.txt文件输入数据,最终的结果输出到output.txt文件中,对该过程有较好的理解
  • 1.回溯法求解 #include<bits/stdc++.h> #define MAXN 102 #define MAXM 102 using namespace std; int n,m,cost; int w[MAXN][MAXM]; int c[MAXN][MAXM]; int bestx[MAXN]; int x[MAXN];...bestw){

    1.回溯法求解

    #include<bits/stdc++.h>
    #define MAXN 102
    #define MAXM 102
    using namespace std;
    int n,m,cost;
    int w[MAXN][MAXM];
    int c[MAXN][MAXM];
    int bestx[MAXN];
    int x[MAXN];
    int cw=0,cc=0;
    int bestw=9999;
    void dfs(int i){
    	if(i>n){
    		if(cw<bestw){
    			bestw=cw;
    			for(int j=1;j<=n;j++){
    				bestx[j]=x[j];
    			}
    		}
    	}else {
    		for(int j=1;j<=m;j++){
    			if(cc+c[i][j]<=cost&&cw+w[i][j]<bestw){
    				x[i]=j;
    				cc+=c[i][j];
    				cw+=w[i][j];
    				dfs(i+1);
    				cc-=c[i][j];
    				cw-=w[i][j];
    			}
    		}
    	}
    }
    int main(){
    	cin>>n>>m>>cost;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>w[i][j];
    		}
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>c[i][j];
    		}
    	}
    	dfs(1);
    	for(int i=1;i<=n;i++){
    		cout<<bestx[i]<<" ";
    	}
    	cout<<endl<<bestw<<endl; 
    }
    

    2.分支限界法

    #include<bits/stdc++.h>
    #define MAXN 102
    #define MAXM 102
    #define INF 0x3f3f3f3f
    using namespace std;
    
    int n,m,cost;
    int w[MAXN][MAXM];
    int c[MAXN][MAXM];
    typedef struct {
    	int no,i,w,c;
    	int x[MAXN];
    }NodeType;
    struct Cmp{
    	bool operator() (const NodeType &s,const NodeType &t){
    		return (s.w>t.w)||(s.w==t.w&&s.c>t.c);
    	}
    };
    int bestw=INF;
    int bestc=INF;
    int bestx[MAXN];
    int Count=1;
    void solve(){
    	NodeType e,e1;
    	priority_queue<NodeType,vector<NodeType>,Cmp> qu;
    	e.no=Count++;
    	e.i=0;e.w=0;e.c=0;
    	memset(e.x,0, sizeof (e.x) );
    	qu.push(e);
    	while(!qu.empty()){
    		e=qu.top();qu.pop();
    		if(e.i==n){
    			if(e.c=cost&&e.c<bestc&&e.w<bestw){
    				bestw=e.w;
    				bestc=e.c;
    				for(int j=1;j<=n;j++){
    					bestx[j]=e.x[j];
    				}
    			}
    		}else{
    			for(int j=1;j<=m;j++){
    				if(e.c+c[e.i+1][j]<=cost&&e.c+c[e.i+1][j]<bestc
    				&&e.w+w[e.i+1][j]<bestw){
    					e1.no=Count++;
    					e1.i=e.i+1;
    					e1.w=e.w+w[e1.i][j];
    					e1.c=e.c+c[e1.i][j];
    					for(int k=1;k<=n;k++){
    						e1.x[k]=e.x[k];
    					} 
    					e1.x[e1.i]=j;
    					qu.push(e1);
    				}
    			}
    		} 
    	} 
    }
    int main(){
    	cin>>n>>m>>cost;
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>w[i][j];
    		}
    	}
    	for(int i=1;i<=n;i++){
    		for(int j=1;j<=m;j++){
    			cin>>c[i][j];
    		}
    	}
    	solve();
    	for(int i=1;i<=n;i++){
    		cout<<bestx[i]<<" ";
    	}
    	cout<<endl<<bestw<<endl; 
    }
    
    展开全文
  • 最小机器重量问题处理 一、回溯法 1.基本概念:  (1)回溯法  回溯算法是一种选优搜索法,按选优条件向前搜索,以达到目标。简单的说是在搜索过程中寻找问题的解,当发现已不满足求解条件时,就回溯返回,尝试别的...

    开门见山

    简单理解回溯法

    最小机器重量问题处理

    一、回溯法

    1.基本概念:

        (1)回溯法

        回溯算法是一种选优搜索法,按选优条件向前搜索,以达到目标。简单的说是在搜索过程中寻找问题的解,当发现已不满足求解条件时,就回溯返回,尝试别的路径。

        当探索到某一步时,发现原先选择不是目前的最优解或不满足问题条件时,就退回一步重新选择,并减去当前步骤的节点对应的值,这种方法为回溯法。

        (2)剪枝函数:

        一般回溯法会走剪枝函数,因为你回溯了,已经走了这个步骤,走过处理的逻辑,当前节点的数据存在参与计算。你退回上一步,则需要减去当前步骤的数据是吧。编写去除这些节点数据的函数就是剪枝函数。

    2.回溯法解题步骤

        (1)针对所给问题,确定问题的解空间: 首先应明确定义问题的解空间,问题的解空间应至少包含问题的一个(最优)解。 

        (2)确定结点的扩展搜索规则 

        (3)以深度优先方式搜索解空间,并在搜索过程中用剪枝函数避免无效搜索。

    二、最小机器重量设计问题

    1.问题描述

        设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设 wij 是从供应商j处购得的部件 i 的重量, cij 是相应的价格。试设计一个算法,给出总价格不超过 c 的最小重量机器设计。

    2.问题分析

        初始化供应商数量及部件数量,然后初始化部件的一些属性作为测试数据。程序关键点是中间变量的总价值sumprice取较小的那个,总重量sumWeight与最小重量c的比对是否达到最小,最优。

        问题是求所选购部件的总价格sumprice不超过c (sumprice < c) 的最小机器重量min{sumweight1, sumweight2} 。这里采用的是穷举法计算所有的组合情况下的总重量及总价值,同时判断总价格不超过c的情况下,比对最小总重量与当前总重量,取较小的一个。

    说明:

        声明变量总重量sumweight为0,初始化第一个最小总重量sumweight为第一个部件在第一家供应商的重量。

        声明变量总价格sumprice为0,初始化第一个总价格sumprice为第一个部件在第一家供应商的重量。

    注意:

        前提是机器由n个部件构成,所以注意要求的部件个数是确定的。

    3.代码实现

    package common.test;
    
    /**
     * 1.最小重量机器设计问题:
     * 		设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。
     * 		设 wij 是从供应商j处购得的部件 i 的重量, cij 是相应的价格。
     * 2.试设计一个算法,给出总价格不超过 c 的最小重量机器设计。
     * @author niaonao
     *
     */
    public class MinWeightMachine {
    
    	//声明相关变量 
    	private static int partweight[][] = new int[110][110];//存放部件重量的数组
    	private static int partprice[][] = new int[110][110];//存放部件价格的数组
    	
    	private static int n_part;		//部件
    	private static int m_supplier;	//供应商
    	private static int C_totalprice;	//总价格
    	private static int answer;		//最后的最小重量
    	private static int sumprice;	//当前部件的总价值
    	private static int sumWeight;	//当前部件的总质量
    	
    	public static void main(String[] args) {
    		answer = Integer.MAX_VALUE;	//初始化最总结果
    		C_totalprice = 11;	//初始化总价格
    		sumprice = 0;sumWeight = 0;
    		
    	    n_part = 2;m_supplier = 2;//初始化供应商及部件
    	    partweight[1][1] = 5;partweight[1][2] = 4;partweight[2][1] = 5;partweight[2][2] = 3;
    	    partprice[1][1] = 3;partprice[1][2] = 10;partprice[2][1] = 6;partprice[2][2] = 8;
    	    
    	    int i = 1;
    	    minWeight(i);
    	    System.out.println("满足总价格不超过 " + C_totalprice + " 的最小重量为 " + answer);
    	    
    	}
    	
    	private static void minWeight(int i)
    	{
    	    if(i == n_part + 1){
    	    	answer = 
    	        		answer > sumWeight ? sumWeight : answer;
        		System.out.println("此时总价格:"+sumprice + "\n此时总质量:"+sumWeight);
    	        return ;
    	    }
    	    
    	    for(int j = 1; j <= m_supplier; j++){
    	        sumprice = sumprice + partprice[i][j];
    	        sumWeight = sumWeight + partweight[i][j];
    	        if(sumprice > C_totalprice || sumWeight > answer){
    	            continue;
    	        }
    	        minWeight(i + 1);	//计算当前值总重量,总价值 
    	        sumprice = sumprice - partprice[i][j];
    	        sumWeight = sumWeight - partweight[i][j];
    	    }
    	    
    	}
    
    }

    4.运行结果



    展开全文
  • 最小机器重量设计问题 题目内容: 设某一机器由n个部件组成,部件编号为1n,每一种部件都可以从m个不同的供应商处购得,供应商编号为1m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器部件...

    最小机器重量设计问题

    题目内容:

    设某一机器由n个部件组成,部件编号为1n,每一种部件都可以从m个不同的供应商处购得,供应商编号为1m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器部件重量和机器部件价格,计算总价格不超过d的最小重量机器设计。(注意:输出结果中第一行最后没有空格。比如下面的输出样例中1 3 1后面没有空格。)

    输入格式:

    第1行输入3个正整数n,m和d。接下来n行输入wij(每行m个整数),最后n行输入cij(每行m个整数),这里1≤n、m≤100。

    输出格式:

    输出的第1行包括n个整数,表示每个对应的供应商编号,第2行为对应的最小重量。

    输入样例:

    3 3 7

    1 2 3

    3 2 1

    2 3 2

    1 2 3

    5 4 2

    2 1 2

    输出样例:

    1 3 1

    4

    时间限制:500ms内存限制:32000kb

    #include <stdio.h>
    typedef struct Firm
    {
    	int weight[10];
    	int price[10];
    }F;
    int main()
    {
    	F firm[10];
    	int n, m, d, count[10] = { 0 }, i = 0, j = 0, k = 0, a[10], b[10], aweight, bweight;
    	scanf("%d %d %d", &n, &m, &d);
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < m; j++)
    		{
    			scanf("%d", &firm[j].weight[i]);
    		}                                    //输入每个厂家对每个部件的价格
    	for (int i = 0; i < n; i++)
    		for (int j = 0; j < m; j++)
    		{
    			scanf("%d", &firm[j].price[i]);
    		}                                    //输入每个厂家对每个部件的重量
    	while (i < n)
    	{
    		if (i == -1)
    		{
    			k == 2;
    			break;
    		}                                    //控制回溯程度
    		if (j == m)
    		{
    			i--;
    			j = a[i];
    			j++;
    			continue;
    		}                                   //当厂家遍历完后进行回溯
    		a[i] = j;                           //记录下每步选择的厂家
    		count[i + 1] = count[i] + firm[j].price[i];
    		if (count[i+1] > d)
    		{
    			j++;
    			continue;
    		}                                   //选择部件厂家判断是否超过预算价
    		else
    		{
    			if (i == n - 1)
    			{
    				if (k == 0)
    				{
    					aweight = 0; bweight = 0;
    					k = 1;
    					for (int m = 0; m < n; m++)
    					{
    						b[m] = a[m];
    						bweight += firm[b[m]].weight[m];
    					}
    				}                           //第一次成功匹配的话将结果记录
    				else
    				{
    					aweight = 0; 
    					for (int m = 0; m < n; m++)
    					{
    						aweight += firm[a[m]].weight[m];
    					}
    					if (aweight < bweight)
    					{
    						for (int m = 0; m < n; m++)
    							b[m] = a[m];
    						bweight = aweight;
    					}                        //后面匹配结果与记录结果比较
    				}
    				if (a[i] == m - 1)
    				{
    					--i;
    					j = a[i];
    					j++;
    					continue;
    				}                             //判断是否遍历到底部然后回溯
    				else
    				{
    					j++;
    				}                             //不是则进行厂家的选择
    			}
    			else
    			{
    				i++;
    				j = 0;
    			}                                  //厂家选择
    		}
    	}
    	if (k == 0)
    		printf("此题无解");
    	else
    	{
    		for (int m = 0; m < n; m++)
    		{
                             b[m]=b[m]+1;
                                 if(m==n-1)
                                {
                                     printf("%d",b[m]);
                                     break;
                                }
                			printf("%d ", b[m] );
    		}
    		printf("\n%d", bweight);
    	}
    }
    
    展开全文
  • 回溯法求解最小机器重量设计问题

    千次阅读 2019-04-06 20:17:24
    求解最小机器重量设计问题 题目内容: 设某一机器由n个部件组成,部件编号为1n,每一种部件都可以从m个不同的供应商处购得,供应商编号为1m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器...

    求解最小机器重量设计问题
    题目内容:

    设某一机器由n个部件组成,部件编号为1n,每一种部件都可以从m个不同的供应商处购得,供应商编号为1m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器部件重量和机器部件价格,计算总价格不超过d的最小重量机器设计。(注意:输出结果中第一行最后没有空格。比如下面的输出样例中1 3 1后面没有空格。)

    输入格式:

    第1行输入3个正整数n,m和d。接下来n行输入wij(每行m个整数),最后n行输入cij(每行m个整数),这里1≤n、m≤100。

    输出格式:

    输出的第1行包括n个整数,表示每个对应的供应商编号,第2行为对应的最小重量。

    输入样例:

    3 3 7

    1 2 3

    3 2 1

    2 3 2

    1 2 3

    5 4 2

    2 1 2

    输出样例:

    1 3 1

    4

    #include<cstdio>
    #include<cstring>
    using namespace std;
    
    #define MAXSIZE 101
    int n,m,d;
    int w[MAXSIZE][MAXSIZE];//存储重量
    int c[MAXSIZE][MAXSIZE];//存储价格
    int x[2][MAXSIZE];//x[j]表示第j个商品所选取的店铺编号
    int min_w=0x7fffffff;//最小的重量
    int weight=0;
    int price=0;
    
    void get_w(int i){//选取第i个商品
    	if(i>n){
    	    if(weight<min_w){//商品都选择完毕,如果小于当前最小值,则替换
    		    min_w=weight;
    			for(int k=1;k<=n;k++){
    				x[0][k]=x[1][k];//x[0]保存当前最小重量的商铺
    			}
    		}
    		weight-=w[i-1][x[1][n]];//回溯,减去最后一件商品的相关重量和价格
    		price-=c[i-1][x[1][n]];
    	}
    	else{
    		int j;
    		for(j=1;j<=m;j++){
    			weight+=w[i][j];
    			price+=c[i][j];
    			if(price<=d){//价格小于d则递归求下一个商品
    				x[1][i]=j;//第i个商品在第j个店铺选取
    				get_w(i+1);
    			}
    			else{
    			 	weight-=w[i][j];//否则回溯
    			 	price-=c[i][j];
    			}
    		}
    		if(j==m+1){
    			weight-=w[i-1][x[1][i-1]];//循环结束再回溯一层
    			price-=c[i-1][x[1][i-1]];
    		}
    	}
    }
    
    int main(){
    	memset(w,0,sizeof(w));//置零
    	memset(c,0,sizeof(c));
    	memset(x,0,sizeof(x));
    	scanf("%d%d%d",&n,&m,&d);//输入初始化
    	
    	for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    			scanf("%d",&w[i][j]);
        for(int i=1;i<=n;i++)
    		for(int j=1;j<=m;j++)
    			scanf("%d",&c[i][j]);
    	get_w(1);
    	
    	for(int k=1;k<n;k++){
    		printf("%d ",x[0][k]);
    	}
    		printf("%d\n",x[0][n]);
    		printf("%d",min_w);
    	return 0;
    }
    

    在这里插入图片描述

    展开全文
  • 对于给定的机器部件重量机器部件价格,计算总价格不超过d的最小重量机器设计。(注意:输出结果中第一行最后没有空格。比如下面的输出样例中1 3 1后面没有空格。) 输入格式: 第1行输入3个正整...
  • ***东北师范大学算法课在线习题11月18日*** Problem Description 设某一机器由n个部件组成,部件编号为1-n...对于给定的机器部件重量机器部件价格,计算总价格不超过cost的最小重量机器设计,可以在同一个供应商...
  • 对于给定的机器部件重量机器部件价格,计算总价格不超过cost的最小重量机器设计, 可以在同一个供应商处购得多个部件。 输入描述 第一行输入3个整数n,m,cost, 接下来n行输入wij(每行m个整数), 最后n行输入cij...
  • 最小重量机器设计问题,使用C++编写,运用了分支限界的思想。
  • 对于给定的机器部件重量机器部件价格,计算总价格不超过cost的最小重量机器设计,可以在同一个供应商处购得多个部件。 【输入描述】 n, m, cost 接下来n行表示wij 最后n行表示cij 【输入】 3 3 7 1 2 3 3 ...
  • 设计一个回溯算法,对于给定的机器部件重量机器部件价格,计算总价格不超过c的最小重量机器设计。 2.算法设计:   回溯法要求要给出约束条件,很明显:总价格不超过c, 设当前已选部件的重量
  • 对于给定的机器部件重量机器部件的价格,计算总价不超过cost的最小重量机器设计,要求在同一个供应商处最多只购得一个部件。 输入描述 第1行输入3个整数,n、m、cost,接下来n行输入w[i][j](每...
  • 算法设计:对于给定的机器部件重量机器部件价格,计算总价值不超过d的最小重量机器设计。 数据输入:第一行由3个正整数n,m,d。接下来的2n行,每行m个数。前n行是c,后n行是w。 结果输出:将计算的最小重量及每...
  • 分支限界法之最小重量机器设计问题 这个算法有些难以理解 主要是你得搞清楚优先级队列的使用 该代码注释详细 分支限界法之最小重量机器设计问题 这个算法有些难以理解 主要是你得搞清楚优先级队列的使用 该代码注释...
  • 1.采用回溯法求解 #include<bits/stdc++.h> #define MAXN 102 #define MAXM 102 using namespace std; int n,m,cost; int w[MAXN][MAXM]; int c[MAXN][MAXM]; int bestx[MAXN]; int x[MAXN];...k++
  • 全都是自己写的,都能跑出来 实打实写的哦~ ...3、用c++语言实现用回溯法、分支限界法解决最小重量机器设计问题,分析时间复杂性; 4、体会回溯法、分支限界法解决问题的基本思路和步骤。 预览地址:
  • 这个回溯不是简单的排序,因为每一个位置都有n种可能,所以是一个特殊的排列,但是其他部分是一样的道理
  • 对于给定的机器部件重量机器部件价格,计算总价格不超过cost的最小重量机器设计,限制只能在同一个供应商处购得一个部件。由于有多种设计的可能,你只需要输出最小重量。(n,m<30, cost<1000, wij,cij<200...
  • 算法实现题 6-4最小重量机器设计问题 问题描述:设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处购来的部件i的重量,cij是相应的价格。 设计一个优先队列式分支定界法,给...
  • 5-3最小重量机器设计问题
  • 算法实现题 5-3 最小重量机器设计问题 问题描述:设某一机器由n个部件组成,每一种部件都可以从m个不同的供应商处购得。设wij是从供应商j处够来的部件i的重量,cij是相应的价格。 试设计一个算法,给出总价格不超过...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 7,407
精华内容 2,962
关键字:

最小机器重量设计问题