Toggle navigation
NKZX_NOI_OJ
常见问答
题库
来源/分类
状态
排名
竞赛&作业
Login
问题1144--0-1 背包问题
1144: 0-1 背包问题
时间限制:
1 Sec
内存限制:
64 MB
提交:
25
解决:
11
[
提交
] [
状态
] [
讨论版
] [命题人:
]
题目描述
有 n 件物品，每件物品有一个重量和一个价值，分别记为 W
1
，W
2
，…，W
n
和 C
1
，C
2
，…，C
n
。现在有一个背包，其容量为 W
K
，要从 n 件物品种任取若干件，要求：
（1） 重量之和小于或等于 W
K
。
（2） 价值之和最大。
输入
第 1 行 2 个整数，表示 n和W
K
，1≤n≤20，1≤W
K
≤10
6
。
第 2 行 n 个整数，表示每一个物品的重量，1≤W
i
≤10
4
。
第 3 行 n 个整数，表示每一个物品的价值，1≤C
i
≤10
8
。
输出
一行一个数，表示符合背包容量的最大价值。
样例输入
Copy
8 200 79 58 86 11 28 62 15 68 83 14 54 79 72 52 48 62
样例输出
Copy
334
来源/分类
穷举算法