大容量背包问题

测试数据来自 system/3005

作业已超过截止时间,您无法递交本题目。

时间限制:1秒  内存限制:256M


【问题描述】

  有 nn 个物品,物品 ii 的体积为 viv_i,价值为 pip_i。要选一些物品装入容量为 cc 的背包(每个物品要么选,要么不选,不能只装一部分),使得背包中物品的价值和最大。

【输入格式】

  第 1 行是整数 nncc,其中1n251 ≤ n ≤ 251c10151 ≤ c ≤ 10^{15}
  接下来的 nn 行,每行两个整数:viv_ipip_i,其中 1vi,pi10151 ≤ v_i,p_i ≤ 10^{15}

【输出格式】

  一个整数,表示能得到的最大价值。

【输入输出样例】

 Input

4 50
20 30
10 20
30 40
20 20

 Output

70

【数据范围】

  1n251 ≤ n ≤ 25
  1c10151 ≤ c ≤ 10^{15}
  1vi,pi10151 ≤ v_i,p_i ≤ 10^{15}

【来源】

  Mr.he

回溯法生成组合练习题

未认领
状态
已结束
题目
10
开始时间
2024-12-01 00:00
截止时间
2025-01-11 23:59
可延期
24.0 小时