计算机算法设计与分析第五章回溯法上机题

淩亂°似流年 2023-10-03 17:52 22阅读 0赞

#### 文章目录 ####

*  7-1 0-1背包 (20 分)
 *   *  题目描述
     *  基本思路
     *  参考代码（dp）
     *  习题答案
 *  7-2 工作分配问题 (20 分)
 *   *  题目描述
     *  参考代码
     *  习题答案
 *  5-3 自然数的拆分 (20 分)
 *   *  题目描述
     *  参考代码
     *  习题答案

## 7-1 0-1背包 (20 分) ##

### 题目描述 ###

给定n(n<=100)种物品和一个背包。物品i的重量是wi，价值为vi，背包的容量为C(C<=1000)。问:应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品i只有两个选择：装入或不装入。不能将物品i装入多次，也不能只装入部分物品i。

输入格式:  
共有n+1行输入： 第一行为n值和c值，表示n件物品和背包容量c； 接下来的n行，每行有两个数据，分别表示第i(1≤i≤n)件物品的重量和价值。

输出格式:  
输出装入背包中物品的最大总价值。

输入样例:  
在这里给出一组输入。例如：

5 10
    2 6
    2 3
    6 5
    5 4
    4 6
    结尾无空行

输出样例:  
在这里给出相应的输出。例如：

15
    结尾无空行

### 基本思路 ###

1.动态规划，填表  
状态转移方程：dp\[j\]=max(dp\[j\],dp\[j-bags\[i\].weight\]+bags\[i\].value);  
[参考：【动态规划】01背包问题（通俗易懂，超基础讲解）][01]  
2.回溯法  
[参考：回溯应用-- 0-1背包问题][-- 0-1]

### 参考代码（dp） ###

//以下为dp 
    #include <iostream>
    using namespace std;
    int dp[1005]={
        0};
    const int maxn=105;
    struct bag{
        
    	int value;
    	int weight;
    };
    bag bags[maxn];
    int main()
    {
        
    	int n,c;
    	cin>>n>>c;
    	for(int i=1;i<=n;i++)
    	{
        
    		cin>>bags[i].weight>>bags[i].value;
    	}
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=c;j>=bags[i].weight;j--)
    		{
        
    		
    			dp[j]=max(dp[j],dp[j-bags[i].weight]+bags[i].value);
    		}
    		
    	}
    //	for(int i=0;i<15;i++)
    //	{
        
    //		cout<<dp[i]<<" ";
    //	}
    //	cout<<endl;
    	cout<<dp[c];
    }

### 习题答案 ###

代码：
    #include <iostream>
    #include <algorithm>
    using namespace std;
    struct Obj {
        
            int weight;
            int value;
    };
    int cp = 0, cw = 0, maxValue = 0;
    int n, c;
    Obj* objs;
    
    //限界函数
    float bound(int i) {
        
            int cleft = c - cw;
            int b = cp;
            while (i <= n && objs[i].weight < cleft) {
        
                    b+= objs[i].value;
                    cleft -= objs[i].weight;
                    i++;
            }
            if (i <= n) {
        
                    b += objs[i].value * cleft / objs[i].weight;
            }
            return b;
    }
    
    //递归回溯函数
    void backtrack(int t) {
        
            if (t > n) {
        //叶子结点，得到问题的一个可能解
                    if (cp > maxValue) {
        
                            maxValue = cp;
                    }
                    return;
            }
            
            //如果满足约束条件进入左子树
            if (cw + objs[t].weight <= c) {
         
                    cw += objs[t].weight;
                    cp += objs[t].value;
                    backtrack(t + 1);
                    cw -= objs[t].weight;
                    cp -= objs[t].value;
            }
            //如果满足限界条件进入右子树
            if (bound(t + 1) > maxValue)
                    backtrack(t + 1);
    }
    
    //用于排序的比较函数，单位价值高的排在前面
    bool cmp(Obj obj1, Obj obj2) {
        
            if (float(obj1.value) / obj1.weight > float(obj2.value) / obj2.weight)
                    return true;
            else
                    return false;
    }
    
    int main() {
        
            int i;
            cin >> n >> c;
            objs = new Obj[n + 1];
            for (i = 1; i <= n; i++) {
        
                    cin >> objs[i].weight>> objs[i].value;
            }
            sort(objs + 1, objs + n + 1, cmp);
            
            backtrack(1);
            cout << maxValue;
            return 0;
    }

## 7-2 工作分配问题 (20 分) ##

### 题目描述 ###

设有n件工作分配给n个人。将工作i分配给第j个人所需的费用为cij 。 设计一个算法，对于给定的工作费用，为每一个人都分配1 件不同的工作，并使总费用达到最小。

输入格式:  
输入数据的第一行有1 个正整数n (1≤n≤20)。接下来的n行，每行n个数，表示工作费用。

输出格式:  
将计算出的最小总费用输出到屏幕。

输入样例:  
在这里给出一组输入。例如：

3
    10 2 3
    2 3 4
    3 4 5
    结尾无空行

输出样例:  
在这里给出相应的输出。例如：

9
    结尾无空行

### 参考代码 ###

#include <iostream>
    using namespace std;
    int min_cost=1e9;
    const int maxn=30;
    bool visit[maxn]={
        false};
    int a[maxn][maxn];
    int n;
    
    
    void dfs(int i,int cur_cost)
    {
        
    	if(i==n+1)
    	{
        
    		if(cur_cost<min_cost)
    		{
        
    			min_cost=cur_cost;
    			
    		}
    		return;
    	}
    	
    	for(int j=1;j<=n;j++)
    	{
        
    		if(!visit[j]&&cur_cost+a[i][j]<min_cost)
    		{
        
    			visit[j]=true;
    			dfs(i+1,cur_cost+a[i][j]);
    			visit[j]=false;
    		}
    	}
    	
    }
    int main()
    {
        
    //	int n;
    	cin>>n;
    //	int a[n+1][n+1];
    	for(int i=1;i<=n;i++)
    	{
        
    		for(int j=1;j<=n;j++)
    		{
        
    			cin>>a[i][j];
    		}
    	}
    	dfs(1,0);
    	cout<<min_cost;
    }

### 习题答案 ###

代码：
    #include <iostream>
    #include <algorithm>
    #include <climits>
    using namespace std;
    int n;
    int cost[21][21]; //n件工作分配给n个人的费用
    int a[21]; 
    int bestc = INT_MAX; //最低总费用
    int cv = 0; //当前分配方案所需的费用
    
    //排列树方法回溯
    void backtrack (int t)
    {
        
    	if (t > n) {
        
    		if (cv < bestc)
    			bestc = cv;
    	} else {
        
    		for (int i=t; i<=n; i++) {
         //访问第i个孩子结点
    			cv += cost[t][a[i]]; //更新第i个孩子结点对应的费用
    			swap (a[t], a[i]);
    
    			//如果当前的费用已经超出前面已经访问过的叶子节点的最低费用则剪枝
    			if (cv < bestc) backtrack(t+1); 
    
    			swap (a[t], a[i]);
    			cv -= cost[t][a[i]];//恢复到父结点对应的状态
    		}
    	}
    }
    
    int main() {
        
    	cin >> n;
    	for (int i = 1; i <= n; i++)
    		for (int j = 1; j <= n; j++)
    			cin >> cost[i][j];
            for (int k = 1; k <= n; k++)
    			a[k] = k;
    
            backtrack(1);
    
            cout << bestc << endl;
            return 0;
     }

## 5-3 自然数的拆分 (20 分) ##

### 题目描述 ###

任何一个大于1的自然数n，总可以拆分成若干个小于n的自然数之和。 当n=7共14种拆分方法：

7=1+1+1+1+1+1+1

7=1+1+1+1+1+2

7=1+1+1+1+3

7=1+1+1+2+2

7=1+1+1+4

7=1+1+2+3

7=1+1+5

7=1+2+2+2

7=1+2+4

7=1+3+3

7=1+6

7=2+2+3

7=2+5

7=3+4

输入格式:  
输入n， 1<n<20。

输出格式:  
按字典序输出具体的方案。

输入样例:  
在这里给出一组输入。例如：

7
    结尾无空行

输出样例:

7=1+1+1+1+1+1+1
    7=1+1+1+1+1+2
    7=1+1+1+1+3
    7=1+1+1+2+2
    7=1+1+1+4
    7=1+1+2+3
    7=1+1+5
    7=1+2+2+2
    7=1+2+4
    7=1+3+3
    7=1+6
    7=2+2+3
    7=2+5
    7=3+4
    结尾无空行

### 参考代码 ###

#include <iostream>
    using namespace std;
    //const int maxn=1e9;
    int a[10000];
    int n;
    void dfs(int x,int y){
        //x:表示第几个盒子    y：表示当前数字还剩多少 
    	if(y==0 &&x>2){
        //x>2是为了防止数拆分为它本身
    		cout<<n<<"=";
    		for(int i=1;i<x-1;i++)
    		{
        
    			cout<<a[i]<<"+";
    		}
    		cout<<a[x-1]<<endl;
    		return;
    	} 
    	
    	for(int i=1;i<=y;i++)
    	{
        
    		if(i>=a[x-1])//后面的数字要大于等于前面的数字 
    		{
        
    			a[x]=i;
    			y-=i;
    			dfs(x+1,y);
    			//回溯“复原”
    			a[x]=0;
    			y+=i;
    		}
    	}
    }
    int main(){
        
    	cin>>n;
    	a[0]=1;
    	dfs(1,n);
    	return 0; 
     }

> 参考：[1318自然数的拆分][1318]

### 习题答案 ###

代码：
    #include <iostream>
    using namespace std;
    //cn表示分解的方案数量
    int left1 = 0;
    int cn = 0;
    int x[10000]; 
    int n;
    void backtrack(int t) {
        
    //当left1的值等于其他数之和时（最少两个数，不是它本身一个数）输出等式。
    	if (left1 == 0 && t > 2) {
        
    		cout << n << "=";
    		for (int i = 1; i < t-1; i++) {
        
    			cout << x[i] << "+";
    		}
    		cout << x[t-1] << endl;
    		cn++;
    		
    		return;
    	}
    //第一次进行时i=x[1-1]=1。当left1的值仍大于零时，递归调用。
    	for (int i = x[t-1]; i <= left1; i++) {
        
    		left1 -= i;
            x[t] = i;
    		if (left1>= 0 )
    			backtrack(t+1);
    		left1 += i;
    	}
    	return;
    }
    
    int main() {
        
    //输入需要拆分的自然数n，并令left1等于n
    	cin >> n;
    	left1 = n;
    	x[0] = 1;
    	backtrack(1);
    	//cout << cn << endl;
    	return 0;
    }

[01]: https://blog.csdn.net/qq_38410730/article/details/81667885
[-- 0-1]: https://blog.csdn.net/qq_21201267/article/details/95123325?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522163852846016780274161975%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fall.%2522%257D&request_id=163852846016780274161975&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~first_rank_ecpm_v1~hot_rank-6-95123325.first_rank_v2_pc_rank_v29&utm_term=01%E8%83%8C%E5%8C%85%E5%9B%9E%E6%BA%AF&spm=1018.2226.3001.4187
[1318]: https://www.bilibili.com/video/BV12z4y117cW?from=search&seid=746427391225468266&spm_id_from=333.337.0.0