#P2871. [USACO07DEC] 魅力手镯
[USACO07DEC] 魅力手镯
题目描述
有 件物品和一个容量为 的背包。第 件物品的重量是 ,价值是 。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。
输入格式
第一行:物品个数 和背包大小 。
第二行至第 行:第 个物品的重量 和价值 。
输出格式
输出一行最大价值。
4 6
1 4
2 6
3 12
2 7
23
注意
n<=2000,m<=100000
有 N 件物品和一个容量为 M 的背包。第 i 件物品的重量是 Wi,价值是 Di。求解将哪些物品装入背包可使这些物品的重量总和不超过背包容量,且价值总和最大。
第一行:物品个数 N 和背包大小 M。
第二行至第 N+1 行:第 i 个物品的重量 Wi 和价值 Di。
输出一行最大价值。
4 6
1 4
2 6
3 12
2 7
23
n<=2000,m<=100000