TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1062
  • 题目
  • P1062代用品装包
    限制 : 时间限制 : 1000 MS   空间限制 : 65536 KB
    问题描述

    设有n种物品,记作A1、A2、…、An,对应于每个Ai(1<=i<=n)都有一个重量Awi和价值Avi(重量和价值都为正整数)。另外,对应于每个Ai,都有一件可代替它的“代用品”Bi,Bi的重量和价值分别为Bwi和Bvi。本题的任务是:选择这n件物品或其代用品的一个子集装进背包,使总重量不超过给定重量TOT,同时使总价值VAL最高。装填的第i步,要么装入Ai,要么装入Bi,要么Ai和Bi都不装。

    输入格式

    第一行:n TOT ,n<=100, TOT<=10000
    第二行:Av1 Aw1 Bv1 Bw1
    第三行:Av2 Aw2 Bv2 Bw2
    ……
    第n+1行:Avn Awn Bvn Bwn

    输出格式

    只有一个数为最大的价值

    样例输入

    2 10  
    3 6 2 3
    6 9 5 10

    样例输出

    16