美しいミズキ

1
输入格式：
2
第一行两个数m,n
3
第2行到第m+1行 对应商品运价
4
第m+2行对应需求量
5
第m+3行对应存货量
6
输出格式：
7
精确到小数点后两位
8

9
eg.
10
6 8
11
6    2    6    7    4    2    5    9
12
4    9    5    3    8    5    8    2
13
5    2    1    9    7    4    3    3
14
7    6    7    3    9    2    7    1
15
2    3    9    5    7    2    6    5
16
5    5    2    2    8    1    4    3
17
35    37    22    32    41    32    43    38
18
60  55  51  43  41  52
19

20
664.00

1
# 运输单价
2
cost = np.zeros((m, n))
3
for i in range(m):
4
    for j in range(n):
5
        cost[i, j] = float(data[idx + j])
6
    idx += n
7

8
# 客户需求量
9
demand = np.array([float(data[idx + i]) for i in range(n)]); idx += n
10

11
# 存量
12
supply = np.array([float(data[idx + i]) for i in range(m)]); idx += m
13

14
# 定义变量
15
x = cp.Variable((m, n),nonneg = True)
16

17
# 定义目标函数
18
objective = cp.Minimize(cp.sum(cp.multiply(cost, x)))
19

20
# 定义约束条件
21
constraints = [
22
    cp.sum(x, axis = 1) <= supply,
23
    cp.sum(x, axis = 0) >= demand
24
]
25

26
# 求解问题
27
prob = cp.Problem(objective, constraints)
28
result = prob.solve()

1
输入格式:
2
第1行输入一个数，n,  表示方阵的大小
3

4
第2行到n+1行，表示n*n的矩阵
5

6
输出格式:
7
输出最优绩效，精度控制在小数点后两位。
8

9
输入示例：
10
5
11
100,0,100,267,100
12
400,200,100,153,33
13
200,800,100,99,33
14
200,0,100,451,34
15
100,0,600,30,800
16

17
输出：
18
2551.00

1
Performance = np.zeros((n, n))
2

3
for i in range(n):
4
    for j in range(n):
5
        Performance[i, j] = float(data[idx])
6
        idx += 1
7

8
# 指派变量，x[i, j] 表示第 i 个人是否做第 j 项工作
9
x = cp.Variable((n, n))
10

11
constraints = [
12
    x >= 0,
13
    x <= 1,
14
    cp.sum(x, axis=1) == 1,  # 每个人完成一个工作
15
    cp.sum(x, axis=0) == 1   # 每个工作只能安排一个人
16
]
17

18
objective = cp.Maximize(cp.sum(cp.multiply(Performance, x)))

1
输入格式:
2

3
第1行输入一个树，n,  表示方阵的大小
4

5
第2行到n+1行，表示n*n的相邻矩阵
6

7
最后一行表示人数
8

9
输出格式:
10
输出最佳人数，最终结果为整数。
11

12
输入示例：
13
7
14
0,1,1,0,0,0,0
15
0,0,1,1,1,0,0
16
0,0,0,1,0,0,0
17
0,0,0,0,1,1,1
18
0,0,0,0,0,1,0
19
0,0,0,0,0,0,1
20
0,0,0,0,0,0,0
21
34, 29, 42, 21, 56, 18, 71
22

23
输出示例：
24
177

1
A = np.zeros((n, n), dtype=int)
2
for i in range(n):
3
    for j in range(n):
4
        A[i, j] = int(data[idx])
5
        idx += 1
6

7
num = np.array([int(data[idx + i]) for i in range(n)])
8

9
# 原矩阵只给了上三角形式，所以转成无向相邻矩阵
10
Adj = ((A + A.T) > 0).astype(int)
11

12
# 主对角线设为 0，因为 t[i, j] 只表示“供应相邻社区”，不表示供应本区
13
np.fill_diagonal(Adj, 0)
14

15
# t[i, j] = 1 表示在 i 区建点，并且供应相邻的 j 区
16
t = cp.Variable((n, n), boolean=True)
17

18
# z[j] = 1 表示第 j 个社区被覆盖
19
# 这里 z 不需要设置 boolean，连续变量即可
20
z = cp.Variable(n)
21

22
# 第 i 行有 1，表示第 i 个社区建了代理点
23
selected = cp.sum(t, axis=1)
24

25
# 第 j 列有 1，表示第 j 个社区被其他代理点供应
26
served_by_neighbor = cp.sum(t, axis=0)
27

28
# 社区 j 被覆盖的次数：
29
# 自己建点覆盖一次 + 被邻居供应覆盖一次
30
covered = selected + served_by_neighbor
31

32
constraints = [
33
    # 一共建立两个代理点
34
    cp.sum(t) == 2,
35

36
    # 每个社区最多建立一个代理点
37
    cp.sum(t, axis=1) <= 1,
38

39
    # 只能供应相邻社区
40
    t <= Adj,
41

42
    # 覆盖变量约束
43
    z >= 0,
44
    z <= 1,
45
    z <= covered
46
]