uva 10498 Happiness 线性规划

缘起

继续学习单纯形法求解线性规划. uva 10498 Happiness

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
将n种食品分给m个参赛选手，一个单位的某食品给某个选手一定的满足度，每个选手有一个最大满足度。为了避免浪
费，分给每一个选手的食品都不超越选手的满足度。已知各种食品的单价，求最多可以花多少钱。

【输入】
多样例. 每个样例包含n和m（(3 ≤ n, m ≤ 20），然后一行包含n个实数, 表示每种食物的单价.
然后是m行，每行刻画了一位选手. 每行n+1个数字, 前n个实数是每种食物能给该选手带来的满足感, 最后那个实数
是该选手最多需要的满足感

【输出】
对每个样例, 输出最多能花费的钱. 最后的答案四舍五入.

【样例输入】
3 3
1 0.67 1.67
1 2 1 430
3 0 2 460
1 4 0 420

【样例输出】
Nasa can spend 1354 taka.

【限制】
3s

红果果的线性规划问题. 上来就是标准型，不需要转换. 直接套单纯形模板.

以样例输入为例：

输入第一行，有3种食品，3个选手。

第二行是每种食品的单价。目标函数求最多可以花多少钱，也就是极大化目标函数

C=x1*1+x2*0.67+x3*1.67

输入后面某个选手，每种食品单位给予的满足度以及他最大满足度。也就是我们的约束条件：

x1*1+x2*2+x3*1<=430

x1*3+x2*0+x3*2<=460

x1*1+x2*4+x3*0<=420

求出的C最后还要乘以m（不晓得为啥, 反正是题意, 但是懒得去解读题意了）

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
//#include "stdafx.h"
#include <stdio.h>
#include <math.h>
//#define LOCAL

const int maxn = 50; // n+m最大值
int n,m;
double a[maxn][maxn], eps = 1e-9, inf = 1e9;

inline int kk(bool x)
{
	return x?1:-1;
}

void pivot(int r, int c)
{
	double t = a[r][c];
	a[r][c] = 1;
	for (int i = 0; i<=n; i++)
	{
		a[r][i]/=t;
	}
	for (int i = 0;i<=m; i++)
	{
		if (abs(a[i][c])>eps && i!=r)
		{
			t = a[i][c];
			a[i][c] = 0;
			for (int j = 0; j<=n; j++)
			{
				a[i][j]+=kk(!i&&!j)*t*a[r][j];
			}
		}
	}
}

void simplex()
{
	int i,j;
	double w,t;
	while(1)
	{
		i = j =0;
		w = -eps;
		for (int k =1;k<=m;k++)
		{
			if (a[k][0]<w)
			{
				i = k;
				w = a[k][0];
			}
		}
		if (!i)
		{
			break;
		}
		for (int k = 1;k<=n; k++)
		{
			if (a[i][k]<-eps)
			{
				j = k;
				break;
			}
		}
		if (!j)
		{
			puts("infeasible");
			return;
		}
		pivot(i,j);
	}
	while(1)
	{
		i = j =0;
		w = eps;
		for (int k =1; k<=n; k++)
		{
			if (a[0][k]>w)
			{
				j = k;
				w = a[0][k];
			}
		}
		if (!j)
		{
			break;
		}
		w = inf;
		for (int k =1;k<=m; k++)
		{
			if (a[k][j]>eps && (t=a[k][0]/a[k][j])<w)
			{
				w = t;
				i = k;
			}
		}
		if (!j)
		{
			puts("unbounded");
			return;
		}
		pivot(i,j);
	}
	printf("Nasa can spend %d taka.\n",(int)(ceil(m*a[0][0])));
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//	freopen("d:\\my.out", "w", stdout);
#endif
	while(~scanf("%d%d", &n,&m))
	{
		a[0][0] = 0;
		for (int i = 1; i<=n; i++)
		{
			scanf("%lf", a[0]+i);
		}
		for (int i = 1;i<=m; i++)
		{
			for (int j = 1; j<=n; j++)
			{
				scanf("%lf", a[i]+j);
			}
			scanf("%lf", a[i]);
		}
		simplex();
	}
	return 0;
}

ac情况

Status Accepted
Time 10ms
Length 1635
Lang C++11 5.3.0
Submitted 2019-10-03 08:05:13
Shared
RemoteRunId 23991776