01背包问题

题目内容

题目描述

有N件物品和一个容量为M的背包,每个物品都有他们的重量和价值。比如第 i 个物品的重量为w[i],价值为v[i]。现在我们要往背包里放这些物品,要求在物品总重量不超过背包容量的情况下,使物品的价值总和最大。

输入描述

输入第一行由两个正整数组N和M组成,含义同题目描述相同,满足N<1000,M<10000。

接下来N行每行都有两个正整数,分别代表第i个物品的重量w[i]和价值v[i],满足w[i]<=M,v[i]<100000。

输出描述

输出共一行,用一个正整数代表在满足要求的情况下物品价值总和的最大值。

样例输入

4 10 2 1 3 3 4 5 7 9

样例输出

12

提示

提交评测
请登录后再操作

题目描述

01背包问题
1102
0
Level2
363
119
33%
证书查询 x
请输入证书编号:

请输入正确的证书编号

学员姓名:孙兴民

课程:Scratch Level 1

发证日期:2019.08.15

证书查询

该证书不存在