Toggle navigation
HUSTOJ
常见问答
问题
来源/分类
状态
排名
竞赛&作业
Login
Language
中文
ئۇيغۇرچە
English
فارسی
ไทย
한국어
问题1259--0-1背包(练习版--时间空间放宽)
1259: 0-1背包(练习版--时间空间放宽)
[命题人 :
]
时间限制 :
2.000
sec
内存限制 :
512 MB
解决: 4
提交: 4
统计
题目描述
有 N 件物品和一个容量为 V 的背包。放入第 i 件物品耗费的空间是 C
i
,得到的价值是 W
i
。求解在不超过容量的前提下,将哪些物品装入背包可使价值总和最大。
输入
第 1 行两个正整数,分别表示 N 和 V,中间用一个空格隔开。
第 2 行 N 个正整数,表示 C
i
,中间用一个空格隔开。
第 3 行 N 个正整数,表示 W
i
,中间用一个空格隔开。
其中:1≤N≤100,1≤V≤10
6
,1≤C
i
≤10000,1≤W
i
≤10000。
输出
一行一个正整数,表示最大的价值总和。
样例输入
Copy
4 20 8 9 5 2 5 6 7 3
样例输出
Copy
16
来源/分类
动态规划