同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

2062_最小重量机器设计问题

2022-5-16 18:18| 发布者: Hocassian| 查看: 53| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-3-89504290251799-Problem List-采集的数据-后羿采集器.html

Pro.ID

2062

Title

最小重量机器设计问题

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=2062

AC

Submit

Ratio

16.13%

时间&空间限制

Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

设某一机器由n个部件组成，每一种部件都可以从m个不同的供应商处购得。设w_ij是从供应商j处购得的部件i的重量，c_ij是相应的价格。对于给定的机器部件重量和机器部件价格，计算总价格不超过d的最小重量机器设计。

输入

输入第一行有三个正整数n ( n ≤ 20 )，m ( m ≤ 20 )和d ( d < 200 )。接下来的2n行，每行n个数。前n行是c，后n行是w。

输出

Description

Input

输入第一行有三个正整数n ( n ≤ 20 )，m ( m ≤ 20 )和d ( d < 200 )。接下来的2n行，每行n个数。前n行是c，后n行是w。

Output

输出最小重量，以及每个部件的供应商。

Sample Input

3 3 4
1 2 3
3 2 1
2 2 2
1 2 3
3 2 1
2 2 2

Sample Output

4
1 3 1

Author

John

样例输入