精华内容
下载资源
问答
  • 这个回溯不是简单的排序,因为每一个位置都有n种可能,所以是一个特殊的排列,但是其他部分是一样的道理
    #include<stdio.h>
    const int maxn=100;
    int n,m,c,cw=0,cp=0,bestw=1000;
    int x[maxn]={0};
    int bestx[maxn];
    struct Node
    {
    int w;
    int p;
    }f[maxn][maxn];
    void DFS(int i)
    {
    if(i>n)
    {
    if(cw<bestw)
    {
    bestw=cw;
    for(int k=1;k<=n;k++)
    bestx[k]=x[k];
    }
    return ;
    }
    else
    {
    for(int j=1;j<=n;j++)
    {
    if(cp+f[i][j].p<=c)
    {
    cp+=f[i][j].p;
    cw+=f[i][j].w;
    x[i]=j;
    DFS(i+1);
    x[i]=0;
    cp-=f[i][j].p;
    cw-=f[i][j].w;
    }
    else continue;
    }
    }


    }
    int main()
    {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    scanf("%d",&n);
    scanf("%d",&m);
    scanf("%d",&c);
    int i,j;
    for( i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    scanf("%d",&f[i][j].p);
    for(i=1;i<=n;i++)
    for(j=1;j<=m;j++)
    scanf("%d",&f[i][j].w);
    DFS(1);
    printf("%d\n",bestw);
    for(int k=1;k<=n;k++)
    printf("%d",bestx[k]);
    return 0;
    }
    展开全文
  • ***东北师范大学算法课在线习题11月18日*** Problem Description 设某一机器由n个部件组成,部件编号为1-n...对于给定的机器部件重量机器部件价格,计算总价格不超过cost的最小重量机器设计,可以在同一个供应商...
                          ***东北师范大学算法课在线习题11月18日***
    

    Problem Description
    设某一机器由n个部件组成,部件编号为1-n,每一种部件都可以从m个供应商处购得,供应商编号为1-m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定的机器部件重量和机器部件价格,计算总价格不超过cost的最小重量机器设计,可以在同一个供应商处购得多个部件。

    Input
    第1行输入3个整数n、m、cost,接下来n行输入wij(每行m个整数)最后n行输入cij(每行m个整数),这里1<=n、m<=100

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

    Sample Input

    3 3 7
    1 2 3
    3 2 1
    2 3 2
    1 2 3
    5 4 2
    2 1 2
    

    Sample Output

    1 3 1
    4
    

    思想:回溯(su)法固定模板

    #include <iostream>
    
    using namespace std;
    
    int n,m,cost;
    int w[105][105],c[105][105];
    int ans[100],p[100];
    int weight,value;
    int minweight = 100000;
    void dfs(int t)
    {
    
        if(t==n+1&&value<=cost)
        {
            if(weight<minweight)
            {
             minweight = weight;
            for(int j=1;j<=n;j++)
                ans[j] = p[j];
    
            }
            return;
        }
        if(value<=cost){
        for(int i=1;i<=m;i++)
        {
            p[t] = i;
            weight+=w[t][i];
            value +=c[t][i];
            dfs(t+1);
            p[t] = 0;
            weight-=w[t][i];
            value -=c[t][i];
        }
        }
    }
    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<<ans[i]<<' ';
        cout<<ans[n]<<endl;
        cout<<minweight;
        return 0;
    }
    
    展开全文
  • 最小机器重量设计问题 题目内容: 设某一机器由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);
    	}
    }
    
    展开全文
  • 2、求解最小机器重量设计问题1 问题描述:设某一机器由n个部件组成,部件编号为1~n,每一种 部件都可以从m个不同的供应商处购得,供应商编号哦1~m。设 wij是从供应商j处购得的部件i的重量,cij 是相应的价格。试设计 ...
  • 回溯法求解最小机器重量设计问题

    千次阅读 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个正整数n,m和d。接下来n行输入...
  • 求解最小机器重量设计问题 题目内容: 设某一机器由n个部件组成,部件编号为1,2,…,n,每一种部件都可以从m个不同的供应商处购得,供应商编号为1~m。设wij是从供应商j处购得的部件i的重量,cij是相应的价格。对于给定...
  • 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){
  • 对于给定的机器部件重量机器部件的价格,计算总价不超过cost的最小重量机器设计,要求在同一个供应商处最多只购得一个部件。 输入描述 第1行输入3个整数,n、m、cost,接下来n行输入w[i][j](每...
  • 对于给定的机器部件重量机器部件价格,计算总价格不超过d的最小重量机器设计。(注意:输出结果中第一行最后没有空格。比如下面的输出样例中1 3 1后面没有空格。) 输入格式: 第1行输入3个正整...
  • 最小机器重量问题处理 一、回溯法 1.基本概念:  (1)回溯法  回溯算法是一种选优搜索法,按选优条件向前搜索,以达到目标。简单的说是在搜索过程中寻找问题的解,当发现已不满足求解条件时,就回溯返回,尝试别的...
  • 对于给定的机器部件重量机器部件价格,计算总价格不超过cost的最小重量机器设计, 可以在同一个供应商处购得多个部件。 输入描述 第一行输入3个整数n,m,cost, 接下来n行输入wij(每行m个整数), 最后n行输入cij...
  • 对于给定的机器部件重量机器部件价格,计算总价格不超过cost的最小重量机器设计,可以在同一个供应商处购得多个部件。 【输入描述】 n, m, cost 接下来n行表示wij 最后n行表示cij 【输入】 3 3 7 1 2 3 3 ...
  • 设计一个回溯算法,对于给定的机器部件重量机器部件价格,计算总价格不超过c的最小重量机器设计。 2.算法设计:   回溯法要求要给出约束条件,很明显:总价格不超过c, 设当前已选部件的重量

空空如也

空空如也

1 2 3 4 5 ... 8
收藏数 156
精华内容 62
关键字:

最小机器重量设计问题