アルゴリズム分析と設計-第2回実験

75651 ワード

データ構造欲が深い DP ダイナミック？プログラムアルゴリズムの設計と分析リュックサックの問題会場の手配問題

文書ディレクトリ

01リュックサック問題

一部リュック問題

会場手配問題

ツリーの最大連通分岐

アルゴリズムの設計と分析の授業の実験、全部で4つの問題、すべてファイルで読み書きして、しかも各問題のランダムなデータの生成方法を提供しました.ブログには、参照用にコードのみが置かれています.
01リュックサックの問題

#include 
#include 
#include 
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 
#include 
#include 
#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 
#include 
#include 
#include 
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 
#include 
#include 
#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 
#include 
#include 
#include 
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 
#include 
#include 
#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 
#include 
#include 
#include 
#include 
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
*/

ランダムツリーデータ生成詳細はブロガーが発表したブログを参照:ランダムツリー生成アルゴリズム(ツリーです!)

#include 
#include 
#include 
#include 
#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 
*/

ブラウザがjquery ajax loadの前進、後退機能をサポートする方法

greasemonkey油サルの初学過程で出会った問題