算法设计与分析代码

本文最后更新于 2021年12月13日 上午

子集和数问题

由于本实验是为了验证数据集影响，因此没有采用一次增加两个的限界函数。此代码左支限界是 w+wi> target,右支限界是w+rest>=target. 并且由于实验网站要求在没有正确解的情况下输出近似解，因此每次触底或者左支终止之后还进行了记录。最后因为进行了排序，而数据集给出的答案中并没有进行排序，因此使用了一个结构体对开始的位置进行记录。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
#include<iostream>
#include<fstream>
#include<vector>
#include<string>
#include <windows.h>
#define N 6
#define MAX_ANS 1000
using namespace std;
struct node
{
    int sum;
    int loc;
};
int time=0;
int ans=0;
int nearest = 0;
int use[MAX_ANS][N+1];
void quick(vector<node>& a, int l, int r)
{
    if(l < r)
    {
        int i=l, j=r, key=a[l].sum;
        while(i<j)
        {
            while(i<j && a[j].sum>=key)
            {
                j--;
            }
            while(i<j && a[i].sum<=key)
            {
                i++;
            }
            swap(a[i], a[j]);
        }
        swap(a[i], a[l]);
        quick(a, l, i-1);
        quick(a, i+1, r);
    }
}
int solve(vector<node> a, int target, int now, int sum, int r)
{
    if(now<0 || now>N-1)
    {
        return 0;
    }
    if(use[ans][now] == 2) //这个节点还没有被访问过
    {
        int temp_sum = sum+a[now].sum;
        if(now == N-1) //触底
        {
            if(temp_sum == target)
            {
                use[ans][now] = 1;
                for(int i=0; i<N; i++)
                {
                    use[ans+1][i] = use[ans][i];
                }
                ans++;
                time++;

            }
            else if(temp_sum < target && (nearest > temp_sum || nearest == 0))
            {
                nearest = temp_sum;
                use[ans][now] = 1;
                for(int i=0; i<N; i++)
                {
                    use[MAX_ANS-1][i] = use[ans][i];
                }

            }
            else//直接转向右支触底
            {
                if(nearest > sum)
                {
                    use[ans][now] = 0;
                    nearest = sum;
                    for(int i=0; i<N; i++)
                    {
                        use[MAX_ANS-1][i] = use[ans][i];
                    }
                }
            }
            use[ans][now] = 2;
            return solve(a, target, now-1, sum, r);
        }

        //没触底的正常处理流程
        if(temp_sum == target) //等于就记录(time++)并且跳过这个节点
        {
            use[ans][now] = 1;
            for(int i=0; i<N; i++)
            {
                use[ans+1][i] = use[ans][i];
            }
            ans++;
            time++;
            return solve(a, target, now, sum+a[now].sum, r-a[now].sum);
        }
        else if(temp_sum < target)
        {
            use[ans][now] = 1;
            return solve(a, target, now+1, sum+a[now].sum, r-a[now].sum);
        }
        else
        {
            use[ans][now] = 2;
            if(now < nearest)
            {
                nearest = now;
                for(int i=0; i<N; i++)
                {
                    use[MAX_ANS-1][i] = use[ans][i];
                }
            }
            return solve(a, target, now-1, sum, r);
        }

    }
    else//回溯
    {
        if(use[ans][now] == 1 && r+now>nearest) //该节点已经访问左支
        {
            use[ans][now] = 0;
            return solve(a, target, now+1, sum-a[now].sum, r+a[now].sum);
        }
        else
        {
            use[ans][now] = 2;
            return solve(a, target, now-1, sum, r);
        }
    }
    return 0;
}
int main()
{
    fstream input_stream;
    input_stream.open("p08_w.txt", ios::in);
    fstream target_stream;
    target_stream.open("p08_c.txt", ios::in);
    fstream ans_stream;
    ans_stream.open("p02_s.txt", ios::in);
    int target ;
    vector<node> sum;
    vector<string> std_ans;
    node temp_flag;
    string temp_string;
    int temp_loc = 0;
    while(!input_stream.eof())
    {
        input_stream>>temp_flag.sum;
        temp_flag.loc = temp_loc++;
        sum.push_back(temp_flag);
    }
    while(!target_stream.eof())
    {
        target_stream>>target;
    }
    while(!ans_stream.eof())
    {
        ans_stream>>temp_string;
        std_ans.push_back(temp_string);
    }
    input_stream.close();
    target_stream.close();
    ans_stream.close();

    for(int i=0; i<MAX_ANS; i++)
    {
        for(int k=0; k<N; k++)
        {
            use[i][k] = 2;
        }
    }
    int len = sum.size();
    quick(sum, 0, len-1);
    int all = 0;
    for(int i=0; i<len; i++)
    {
        all+=sum[i].sum;
    }
    LARGE_INTEGER start_time, end_time, tc;
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&start_time);
    solve(sum, target, 0, 0, all);
    QueryPerformanceCounter(&end_time);
    double duration_time = (double)(end_time.QuadPart-start_time.QuadPart) / tc.QuadPart;
    cout<<duration_time<<endl;
    for(int i=0; i<time; i++)
    {
        for(int k=0; k<N; k++)
        {
            if(use[i][k] == 2)
            {
                cout<<0<<" ";
            }
            else
            {
                cout<<use[i][k]<<" ";
            }
        }
        cout<<endl;
    }
    cout<<endl;

    int *print_ans = new int[len];
    for(int i=0; i<time; i++)
    {
        for(int k=0; k<N; k++)
        {
            temp_loc = sum[k].loc;
            int temp = use[i][k];
            if(temp == 2)
            {
                print_ans[temp_loc] = 0;
            }
            else
            {
                print_ans[temp_loc] = temp;
            }
        }
        for(int k=0; k<N; k++)
        {
            cout<<print_ans[k]<<" ";
        }
        cout<<endl;
    }
    if(time == 0)
    {
        for(int i=0; i<N; i++)
        {
            int temp = use[MAX_ANS-1][i];
            if(temp == 2)
            {
                print_ans[sum[i].loc] = 0;
            }
            else
            {
                print_ans[sum[i].loc] = temp;
            }
        }
        for(int i=0; i<N; i++)
        {
            cout<<print_ans[i]<<" ";
        }
    }
    delete [] print_ans;
    return 0;
}

01背包问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
#include<iostream>
#include <windows.h>
#include <iomanip>
#include <time.h>
using namespace std;
#include <algorithm>
 
int w[16] = {0,70,73,77,80,82,87,90,94,98,106,1110,113,115,118,120};			//商品的重量 
int v[16] = {0,135,139,149,150,156,163,173,184,192,201,210,214,221,229,240};			//商品的价值
int bagV = 750;					        //背包大小
int dp[16][751] = { { 0 } };			        //动态规划表
int item[7];					        //最优解情况
 
void findMax() {					//动态规划
	for (int i = 1; i <= 15; i++) {
		for (int j = 1; j <= bagV; j++) {
			if (j < w[i])
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - w[i]] + v[i]);
		}
	}
}
 
void findWhat(int i, int j) {				//最优解情况
	if (i >= 0) {
		if (dp[i][j] == dp[i - 1][j]) {
			item[i] = 0;
			findWhat(i - 1, j);
		}
		else if (j - w[i] >= 0 && dp[i][j] == dp[i - 1][j - w[i]] + v[i]) {
			item[i] = 1;
			findWhat(i - 1, j - w[i]);
		}
	}
}
 
void print() {
	for (int i = 0; i < 16; i++)			//最优解输出
		cout << item[i] << ' ';
	cout << endl;
}
 
int main()
{
	LARGE_INTEGER start_time, end_time, tc;
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&start_time);
	findMax();
	findWhat(15, 750);
	QueryPerformanceCounter(&end_time);
    double duration_time = (double)(end_time.QuadPart-start_time.QuadPart) / tc.QuadPart;
    cout<<duration_time<<endl; 
	print();
	return 0;
}

多源最短路问题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<iostream>
#include<fstream>
#include<windows.h>
#define MAX_SUM 1000
#define MAX 0x3f3f3f3f 
#define N 6
using namespace std;

int m[MAX_SUM][MAX_SUM];
void solve()
{
    for(int k=0; k<N; k++)
    {
        for(int i=0; i<N; i++)
        {
            for(int j=0; j<N; j++)
            {
                m[i][j] = min(m[i][j], m[i][k]+m[k][j]);
            }
        }
    }
}

int main()
{
	for(int i=0; i<MAX_SUM; i++)
	{
		for(int k=0; k<MAX_SUM; k++)
		{
			m[i][k] = MAX;
		}
	}
    fstream input_stream;
    input_stream.open("p0.txt", ios::in);
    while(!input_stream.eof())
    {
        int from, to;
        double sum;
        input_stream>>from;
        input_stream>>to;
        input_stream>>sum;
        m[from][to] = sum;
    }
    input_stream.close();
    LARGE_INTEGER start_time, end_time, tc;
    QueryPerformanceFrequency(&tc);
    QueryPerformanceCounter(&start_time);
    solve();
    QueryPerformanceCounter(&end_time);
    double duration_time = (double)(end_time.QuadPart-start_time.QuadPart) / tc.QuadPart;
    cout<<duration_time<<endl;
    return 0;
}
杂项
算法设计与分析代码
https://www.xinhecuican.tech/post/fb98053e.html
作者
星河璀璨
发布于
2020年12月14日
许可协议