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

1945_算法设计例题：二维背包

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

摘要:

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

Pro.ID

1945

Title

算法设计例题：二维背包

Title链接

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

AC

126

Submit

399

Ratio

31.58%

时间&空间限制

Time Limit: 8000/4000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

给出一个背包，背包有体积容量C和重量限制L，再给出N个物品，每个物品有体积V_i，重量W_i，价值P_i三个参数。每个物品有且仅有一件，求用背包装物品，能获得的最大总价值是多少。

输入

文件的第一行一个数T，表示测试用例子数。接下来T个测试用例。

每个测试用例第一行三个数，N，C，L （0 < N, C, L < 1000）。

接下来N行，每行三个数V_i，W_i，P_i（V_i < 1.5×C, W_i < 1.5×L, P_i < 1000）分别表示物品的体积，重量，价值三个属性。

输出

Description

Input

文件的第一行一个数T，表示测试用例子数。接下来T个测试用例。

每个测试用例第一行三个数，N，C，L （0 < N, C, L < 1000）。

接下来N行，每行三个数V_i，W_i，P_i（V_i < 1.5×C, W_i < 1.5×L, P_i < 1000）分别表示物品的体积，重量，价值三个属性。

Output

为每个测试用例输出一行结果：所装物品价值的最大值。

Sample Input

1
3 5 5
2 3 1
3 2 1
3 3 3

Sample Output

Author

AnzerWall

样例输入