TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P5991
  • 题目
  • P5991【原题的欢乐赛】背包问题+
    限制 : 时间限制 : - MS   空间限制 : 262144 KB
    评测说明 : 1s,256MB
    问题描述

    动态规划习题中有很多道“背包问题”,而这次考试考了一道原题,考场上一片欢呼。

    nodgd仓库里有$n$个物品,第$i$个物品体积为$v_i$,价值为$w_i$。nodgd有一个容积无穷大的背包,背包可以装任意多的物品,没有限制。

    现在nodgd要去深山中度假,为了在旁人眼中显得自己准备得很充分,nodgd想在背包中装入总体积不小于$V$的一些物品。如果装入的物品过于贵重,路上如果遇到强盗、劫匪、山贼等就很亏。所以nodgd想知道总体积不小于$V$的前提下,物品的总价值最小是多少。

    输入格式

    第一行两个整数$n,V$,表示物品的数量和总体积需求。

    接下来$n$行,每行两个整数$v_i,w_i$,表示第$i$种物品的体积和价值。保证所有物品总体积不小于$V$。

    输出格式

    输出一个整数,表示答案。

    样例输入 1

    3 6
    2 5
    3 4
    4 3

    样例输出 1

    7

    样例输入 2

    6 10
    2 4
    3 4
    4 5
    5 11
    6 10
    7 11

    样例输出 2

    15

    提示

    样例说明1
    选择第2和第3个物品。

    样例说明2
    选择第3和第5个物品,或者第2和第6个物品。

    数据规模与约定
    对于50%的数据,$1\leq n\leq200, 1\leq V\leq 10^4, 1\leq v_i,w_i\leq 200$;
    对于100%的数据,$1\leq n\leq 200, 1\leq V\leq 10^6, 1\leq v_i\leq 10^6, 1\leq w_i\leq 200$。保证所有物品总体积不小于$V$。


    来源  感谢nodgd