问题1606--【课课通-例题】9.7.8 0-1背包问题

_{[命题人 : ]}

时间限制 : 1.000 sec 内存限制 : 128 MB

有n件物品，每件物品有一个重量和一个价值，分别记为W1，W2，…，Wn和C1，C2，…，Cn。
现在有一个背包，其容量为Wk，要从n件物品中任取若干件，要求：
（1）重量之和小于或等于W_k。
（2）价值之和最大。

第1行2个整数，表示n和W_k，1≤n≤20,1≤W_k≤10⁵。
第2行n个整数，表示每一个物品的重量，1≤W_i≤10⁴。
第3行n个整数，表示每一个物品的价值，1≤C_i≤10⁸。

一行一个数，表示重量之和小于或等于Wk，的最大价值和。

8 200
79 58 86 11 28 62 15 68
83 14 54 79 72 52 48 62

提交