算法分析与设计-第二次实验

小鱼儿 2022-02-25 15:52 288阅读 0赞

### 文章目录 ###

*   *  01背包问题
     *  部分背包问题
     *  会场安排问题
     *  树的最大连通分支

算法设计与分析课的实验，一共四道题目，都是用文件读写，并且给出了每道题的随机数据生成方法。博客仅放上代码，以供参考。

--------------------

## 01背包问题 ##

#include <iostream>
    #include <fstream>
    #include <ctime>
    using namespace std;
    
    const int maxn = 100005;
    
    void solve(string filename)
    { 
    	int n, c, w[maxn], v[maxn], res[maxn] = { };
    	fstream infile(filename.c_str());
    	infile >> n >> c;
    	cout << "n = " << n << " c = " << c << endl;
    	for (int i = 0; i < n; ++i) { 
    		infile >> w[i];
    	}
    	for (int i = 0; i < n; ++i) { 
    		infile >> v[i];
    	}
    	clock_t start, end;
    	start = clock();
    	for (int j = 0; j < n; ++j) { 
    		for (int i = c; i >= 0; --i) { 
    			if (i >= w[j])
    				res[i] = max(res[i - w[j]] + v[j], res[i]);
    		}
    	}
    	cout << "The ans = " << res[c] << endl;
    	end = clock();
    	cout << "The time = " << end - start << " ms" << endl << endl << endl;
    }
    
    int main() { 
    	solve("forBags5_10.txt");
    	solve("forBags100_10000.txt");
    	solve("forBags1000_100000.txt");
    }
    /* 5 10 2 2 6 5 4 6 3 5 4 6 */

随机数据生成：

#include <iostream>
    #include <cstdlib>
    #include <fstream>
    #define random(a, b) rand()%(b-a+1) + a
    using namespace std;
    
    void creatData100_10000()
    { 
    	fstream outfile("forBags100_10000.txt", ios::out);
    	outfile << 100 << ' ' << 10000 << ' ';
    	for (int i = 0; i < 100; ++i) { 
    		outfile << random(10, 300) << ' ';
    	}
    	for (int i = 0; i < 100; ++i) { 
    		outfile << random(50, 100) << ' ';
    	}
    }
    
    void creatData1000_100000()
    { 
    	fstream outfile("forBags1000_100000.txt", ios::out);
    	outfile << 1000 << ' ' << 100000 << ' ';
    	for (int i = 0; i < 1000; ++i) { 
    		outfile << random(10, 300) << ' ';
    	}
    	for (int i = 0; i < 1000; ++i) { 
    		outfile << random(50, 100) << ' ';
    	}
    }
    
    int main()
    { 
    	creatData100_10000();
    	creatData1000_100000();
    }

--------------------

## 部分背包问题 ##

#include <iostream>
    #include <fstream>
    #include <algorithm>
    #include <ctime>
    using namespace std;
    
    const int maxn = 100005;
    
    bool cmp(pair<int, int> x, pair<int, int> y) { 
    	return ((double)x.second / (double)x.first) > ((double)y.second / (double)y.first);
    }
    
    void solve(string filename)
    { 
    	int n, c;
    	pair<int, int> bags[maxn];
    	double ans = 0.0;
    	fstream infile(filename.c_str());
    	infile >> n >> c;
    	cout << "n = " << n << " c = " << c << endl;
    	for (int i = 0; i < n; ++i) { 
    		infile >> bags[i].first;
    	}
    	for (int i = 0; i < n; ++i) { 
    		infile >> bags[i].second;
    	}
    	clock_t start, end;
    	start = clock();
    	sort(bags, bags + n, cmp);
    	for (int i = 0; i < n; ++i) { 
    		if (bags[i].first > c) { 
    			break;
    		}
    		c -= bags[i].first;
    		ans += bags[i].second;
    	}
    	ans += bags[n - 1].second * c / bags[n - 1].first;
    	cout << "The ans = " << ans << endl;
    	end = clock();
    	cout << "The time = " << end - start << " ms" << endl << endl << endl;
    }
    
    int main() { 
    	solve("forBags5_10.txt");
    	solve("forBags100_10000.txt");
    	solve("forBags1000_100000.txt");
    	solve("forBags100000_100000.txt");
    }

随机数据生成

#include <iostream>
    #include <cstdlib>
    #include <fstream>
    #define random(a, b) rand()%(b-a+1) + a
    using namespace std;
    
    void creatData100_10000()
    { 
    	fstream outfile("forBags100_10000.txt", ios::out);
    	outfile << 100 << ' ' << 10000 << ' ';
    	for (int i = 0; i < 100; ++i) { 
    		outfile << random(10, 300) << ' ';
    	}
    	for (int i = 0; i < 100; ++i) { 
    		outfile << random(50, 100) << ' ';
    	}
    }
    
    void creatData1000_100000()
    { 
    	fstream outfile("forBags1000_100000.txt", ios::out);
    	outfile << 1000 << ' ' << 100000 << ' ';
    	for (int i = 0; i < 1000; ++i) { 
    		outfile << random(10, 300) << ' ';
    	}
    	for (int i = 0; i < 1000; ++i) { 
    		outfile << random(50, 100) << ' ';
    	}
    }
    
    void creatData100000_100000()
    { 
    	fstream outfile("forBags100000_100000.txt", ios::out);
    	outfile << 100000 << ' ' << 100000 << ' ';
    	for (int i = 0; i < 100000; ++i) { 
    		outfile << random(10, 300) << ' ';
    	}
    	for (int i = 0; i < 100000; ++i) { 
    		outfile << random(50, 100) << ' ';
    	}
    }
    
    int main()
    { 
    	creatData100_10000();
    	creatData1000_100000();
    	creatData100000_100000();
    }

--------------------

## 会场安排问题 ##

#include <iostream>
    #include <algorithm>
    #include <fstream>
    #include <ctime>
    using namespace std;
    
    const int maxn = 1000005;
    pair<int, int> line[maxn];
    int n;
    
    bool cmp(pair<int, int> x, pair<int, int> y) { 
    	if (x.second != y.second) return x.second < y.second;
    	return x.first < y.first;
    }
    
    void solve(string filename)
    { 
    	fstream infile(filename.c_str());
    	infile >> n;
    	for (int i = 0; i < n; ++i) { 
    		infile >> line[i].first >> line[i].second;
    	}
    	clock_t start, end;
    	start = clock();
    	sort(line, line + n, cmp);
    	int m = 0, ans = 0;
    	while (m != n) { 
    		int tmp = 0;
    		for (int i = 0; i < n; ++i) { 
    			if (line[i].first >= tmp) { 
    				tmp = line[i].second;
    				line[i].first = line[i].second = -1;
    				m++;
    			}
    		}
    		ans++; 
    	}
    	cout << "n = " << n << endl;
    	cout << "ans = " << ans << endl;
    	end = clock();
    	cout << "time = " << end - start << " ms" << endl << endl;
    }
    
    int main() { 
    	solve("data100.txt");
    	solve("data10000.txt");
    	solve("data30000.txt");
    }
    /* 5 1 23 12 28 25 35 27 80 36 50 */

随机数据生成

#include <iostream>
    #include <cstdlib>
    #include <fstream>
    #define random(a, b) rand()%(b-a+1) + a
    using namespace std;
    
    void creatData(string filename, int n) { 
    	fstream outfile(filename.c_str(), ios::out);
    	outfile << n << ' ';
    	for (int i = 0, x, y; i < n; ++i) { 
    		x = random(1, n*10);
    		y = random(x + 1, n*10);
    		outfile << x << ' ' << y << ' ';
    	}
    }
    
    int main()
    { 
    	creatData("data100.txt", 100);
    	creatData("data10000.txt", 10000);
    	creatData("data30000.txt", 30000);
    }

--------------------

## 树的最大连通分支 ##

#include <iostream>
    #include <vector>
    #include <fstream>
    #include <cstring>
    #include <ctime>
    using namespace std;
    
    const int maxn = 100005;
    vector<int> con[maxn];
    int val[maxn] = { }, maxAns;
    bool vis[maxn] = { };
    fstream outfile("output.txt", ios::out);
    
    int treeIt(int root) { 
    	vis[root] = true;
    	int ans = 0;
    	int len = con[root].size();
    	for (int i = 0, tmp; i < len; ++i) { 
    		if (vis[con[root][i]]) continue;
    		tmp = treeIt(con[root][i]);
    // cout << "root = " << root << " sub = "<< con[root][i] << " tmp = " << tmp << endl;
    		ans += tmp;
    	}
    	ans += val[root];
    	maxAns = max(maxAns, ans);
    // cout << "tmp ans = " << ans << endl;
    // cout << "tmp maxAns = " << maxAns << endl;
    	return (ans > 0 ? ans : 0);
    }
    
    void solve(string filename)
    { 
    	for (int i = 0; i < maxn; ++i) { 
    		con[i].clear();
    	}
    	memset(vis, false, sizeof(vis));
    	int n;
    	fstream infile(filename.c_str());
    	infile >> n;
    	for (int i = 1; i <= n; ++i) { 
    		infile >> val[i];
    	}
    	for (int i = 0, x, y; i < n - 1; ++i) { 
    		infile >> x >> y;
    		con[x].push_back(y);
    		con[y].push_back(x);
    	}
    	clock_t start, end;
    	start = clock();
    	int ans = treeIt(1);
    // cout << "ans = " << ans << endl;
    	cout << "n = " << n << endl;
    	outfile << "n = " << n << endl;
    	cout << "maxAns = " << maxAns << endl;
    	outfile << "maxAns = " << maxAns << endl;
    	end = clock();
    	cout << "time = " << end - start << " ms" << endl << endl;
    	outfile << "time = " << end - start << " ms" << endl << endl;
    }
    
    int main() { 
    	solve("creatTree5.txt");
    	solve("creatTree10.txt");
    	solve("creatTree1000.txt");
    	solve("creatTree10000.txt");
    	solve("creatTree100000.txt");
    }
    /* 5 -1 1 3 1 -1 4 1 1 3 1 2 4 5 */

随机树数据生成  
详见博主发布的博客：[随机树生成算法（就是树！）][Link 1]

#include <iostream>
    #include <fstream>
    #include <cstdlib>
    #include <queue>
    #define random(a, b) rand()%(b-a+1) + a
    using namespace std;
    
    void creatData(int n, string filename) { 
    	fstream file(filename.c_str(), ios::out);
    	int *tree = new int [n];
    	for (int i = 0; i < n; ++i) { 
    		tree[i] = i + 1;
    	}
    	int root = random(0, n - 1);
    	swap(tree[root], tree[n - 1]);
    	int nxt_idx = n - 2;
    	queue<int> Que;
    	file << n << endl;
    	for (int i = 0; i < n; ++i) { 
    		file << random(-1024, 1024) << ' ';
    	}
    	file << endl;
    	Que.push(tree[n - 1]);
    	while (!Que.empty()) { 
    		int now = Que.front();
    		Que.pop();
    		int cnt = random(1, 3);
    		for (int i = 0; i < cnt; ++i) { 
    			int tmp_idx = random(0, nxt_idx); 
    			swap(tree[tmp_idx], tree[nxt_idx]);
    			file << now << ' ' << tree[nxt_idx] << endl;
    			Que.push(tree[nxt_idx]);
    			nxt_idx--;
    			if (nxt_idx == -1) break;
    		}
    		if (nxt_idx == -1) break;
    	}
    }
    
    int main()
    { 
    	creatData(10, "creatTree10.txt");
    	creatData(1000, "creatTree1000.txt");
    	creatData(10000, "creatTree10000.txt");
    	creatData(100000, "creatTree100000.txt");
    	creatData(1000000, "creatTree1000000.txt");
    }
    /* 一个生成随机树（此树非彼数）的算法，树的结点编号从1开始，这个算法生成了树的结点个数、树的结点的权值、树的每条边的结点。 如下面是一棵10结点的二叉树的生成结果： 10 -23 -44 -51 -9 13 51 62 11 -63 19 6 9 6 4 9 2 9 3 4 7 4 1 2 5 2 8 3 10 */

[Link 1]: https://blog.csdn.net/wjh2622075127/article/details/88969312