algorithm期末考试

简单背包问题

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
#include <iostream>

using namespace std;
int data[100];

int weight(int w, int n)//w是重量,n是剩下的件数
{
if (w == 0) {
return 1;
}
if (w!=0&&n == 0) {
return 0;
}
if (weight(w - data[n], n - 1)) {
return 1;
} else {
return weight(w, n - 1);
}
}

int main() {
int w, n;
while (cin>>w>>n) {
for (int i = 1; i <= n; i++) {
cin >> data[i];
}
if (weight(w, n)) {
cout << "YES" << endl;
} else {
cout << "NO" << endl;
}
}
}

Buyer

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
/*
输入1:可以支配的钱和可以选择的物品种类数
输入2:N行,每行为每种物品的价钱和受欢迎程度
输出1:可能达到的最大的受欢迎程度
输出2:购买的物品的编号(物品不重复购买)
*/
#include <iostream>

using namespace std;
typedef struct Food {
int m_money;
int m_value;
} Food;
Food food[1000];
int F[1000][1000] = {0};

int maxlove(int n, int money) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= money; j++) {
if ((j - food[i].m_money) >= 0) {
F[i][j] = max(F[i - 1][j], F[i - 1][j - food[i].m_money] + food[i].m_value);
} else {
F[i][j] = F[i - 1][j];
}
}
}
return F[n][money];
}

int main() {
int money, n;
while (cin >> money >> n) {
food[0].m_money = 0;
food[0].m_value = 0;
for (int i = n; i >= 1; i--) {
cin >> food[i].m_money >> food[i].m_value;
}
int result=maxlove(n,money);
cout << result << endl;//n是种类总数,money是钱
if(result==0)
continue;
int remain = money;
int flag=0;
for (int i = n; i >= 1; i--) {
if (remain >= food[i].m_money) {
if (F[i][remain] - F[i - 1][remain - food[i].m_money] == food[i].m_value) {
remain = remain - food[i].m_money;
if(flag==0)
{
cout << n - i + 1;
flag=1;
}
else
cout <<" "<< n - i + 1;
}
}
}
cout<<endl;
}
}

Renting Boats

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
#include<iostream>
/*
假设输入数据为:
4
5 14 23
5 12
8
以下为输入的数据分布(即m[i][j])
租船点\还船点
0 1 2 3
0 0 5 14 23
1 0 0 5 12
2 0 0 0 8
3 0 0 0 0
p[i][j]:
租船点\还船点
0 1 2 3
0 0 5 10 17
1 0 0 5 12
2 0 0 0 8
3 0 0 0 0
*/
using namespace std;


int main() {
int n;
cin >> n;
int m[200][200] = {0};
int p[200][200] = {0};
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
cin >> m[i][j];
}
}
for (int i = 0; i < n; i++) {
int minNum = m[0][i];
for (int j = 0; j < i; j++) {
minNum = min(minNum, p[0][j] + m[j][i]);
}
p[0][i] = minNum;
}
cout << p[0][n - 1]<<endl;
}

Shortest path counting

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <iostream>
using namespace std;
int P[100][100];
int main(){
int n;
cin>>n;
for(int i=0;i<n;i++){
P[0][i]=1;
P[i][0]=1;
}
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
P[i][j]=P[i-1][j]+P[i][j-1];
}
}
cout<<P[n-1][n-1]<<endl;
}

Coin-collecting by robot

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
using namespace std;
int main()
{
int n,m;
cin>>n>>m;
int map[1000][1000]={0};
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
cin>>map[i][j];
for(int i=1;i<m;i++){
map[0][i]=map[0][i-1]+map[0][i];
}
for(int i=1;i<n;i++){
map[i][0]=map[i-1][0]+map[i][0];
}
for(int i=1;i<n;i++)
for(int j=1;j<m;j++)
map[i][j]=max(map[i-1][j],map[i][j-1])+map[i][j];
cout<<map[n-1][m-1];
cout<<"\r\n";
}

Soldiers

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n,x[10001],y[10001];
int xs,ys;
while(cin>>n){
for(int i=0;i<n;i++){
cin>>x[i]>>y[i];
}
sort(x,x+n);
sort(y,y+n);
for(int i=0;i<n;i++){
x[i]-=i;
}
sort(x,x+n);
xs=ys=0;
for(int i=0;i<n;i++){
xs+=abs(x[i]-x[n/2]);
ys+=abs(y[i]-y[n/2]);
}
cout<<xs+ys<<endl;
}
}

Independent Task Scheduling

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
#include <iostream>

using namespace std;
int dp[202][10000];//dp[i][j] 表示前i个作业中A机器花j分钟的时候 B机器所花时间
int main() {
int n;
cin >> n;
int a[200], b[200];
int sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
sum += a[i];
}
for (int i = 1; i <= n; i++) {
cin >> b[i];
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= sum; j++) {
if (j < a[i]) {//A机器时间不足,只能用B的
dp[i][j] = dp[i - 1][j] + b[i];
} else {
//dp[i][j] = dp[i-1][j]+b[i]代表第i个任务交给B来做,所以做完前i个任务的时候,A机器和前i - 1的任务一样,还是花了j分钟,而B机器则花dp[i-1][j]+b[i]分钟;
//dp[i][j] = dp[i-1][j-a[i]]代表第i个任务交给A来做,现在的A机器花费时间是j,所以在前i - 1个任务完成的时候,A机器是花了j-a[i]分钟的,所以现在B机器还是花了dp[i-1][j-a[i]]分钟;
dp[i][j] = min(dp[i - 1][j] + b[i], dp[i - 1][j - a[i]]);
}
}
}
int ans = 999999;
//max(dp[n][i],i) 表示完成前n个作业A机器花i分钟 B机器花dp[n][i]分钟情况下,最迟完工时间
for (int i = 0; i <= sum; i++)
ans = min(ans, max(dp[n][i], i));
cout << ans << endl;
return 0;
}

Arbitrage

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
#include <iostream>
#include <map>

using namespace std;
map<string, int> money;
double rates[100][100];
int n;

int Arbitrage() {
for (int k = 0; k < n; k++) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
double tmp = rates[i][k] * rates[k][j];
rates[i][j] = max(tmp, rates[i][j]);
if (rates[i][j] * rates[j][i] > 1) {
return 1;
}
}
}
}
return 0;
}

int main() {
int flag = 0, countt = 1;
while (cin >> n && n) {
for (int i = 0; i < n; i++) {
string temp;
cin >> temp;
money[temp] = i;
rates[i][i] = 1;
}
int m;
cin >> m;
for (int i = 0; i < m; i++) {
string a, b;
double rate;
cin >> a >> rate >> b;
rates[money[a]][money[b]] = rate;
}
flag = Arbitrage();
if (flag)
cout << "Case " << countt++ << " Yes" << endl;
else
cout << "Case " << countt++ << " No" << endl;

}
return 0;
}

求最小生成树(Prim算法)

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
#include<iostream>
#include<cstring>
#define inf 32767

using namespace std;

typedef struct {
int n;
int e;
char data[500];
int edge[500][500];
} Graph;

typedef struct {
int index;
int cost;
} mincost;

typedef struct {
int x;
int y;
int weight;
} EDGE;


typedef struct {
int index;
int flag;
} F;

void create(Graph &G, int n, int e) {
int i, j, k, w;
char a, b;
for (i = 0; i < n; i++)
cin >> G.data[i];
for (i = 0; i < n; i++)
for (j = 0; j < n; j++) {
if (i == j)
G.edge[i][j] = 0;
else
G.edge[i][j] = inf;//模板里是G.edge[i][j]=100;
}

for (k = 0; k < e; k++) {
cin >> a;
cin >> b;
cin >> w;
for (i = 0; i < n; i++)
if (G.data[i] == a) break;
for (j = 0; j < n; j++)
if (G.data[j] == b) break;

G.edge[i][j] = w;
G.edge[j][i] = w;
}
G.n = n;
G.e = e;
}


void Prim(Graph &G, int v) {
int lowcost[100];
int min, closest[100], i, j, k;
for (i = 0; i < G.n; i++) {
lowcost[i] = G.edge[v][i];
closest[i] = v;
}
for (i = 1; i < G.n; i++) {
min = inf;
for (j = 0; j < G.n; j++) {
if (lowcost[j] && lowcost[j] < min) {
min = lowcost[j];
k = j;
}
}
cout << '(' << G.data[closest[k]] << ',' << G.data[k] << ')';
lowcost[k] = 0;
for (j = 0; j < G.n; j++)
if (G.edge[k][j] && G.edge[k][j] < lowcost[j]) {
lowcost[j] = G.edge[k][j];//更新距离
closest[j] = k;
}
}
}


int main() {
Graph my;
int n, e;
cin >> n >> e;
create(my, n, e);
Prim(my, 0);
return 0;
}