OJ现已增加邮箱找回密码功能，还没有绑定邮箱的同学们请抓紧时间，以免密码丢失无法找回


问题1259--背包问题

1259: 背包问题

时间限制: 1 Sec  内存限制: 128 MB
提交: 1676  解决: 749
[提交] [状态] [讨论版] [命题人:]

题目描述

给定n件物品和一个容量为C的背包，物品i的重量是Wi,价值为Vi。试求如何选择装入背包的物品，使得物品的总价值最大。

输入

第一行输入一个整数C（0<C<10^9），表示背包容量。
第二行输入n(n<=15),表示物品个数
第三行输入n个整数，wi表示第i个物品的重量(0<wi<10^9)
第四行输入n个整数，vi表示第i个物品的价值(0<vi<10^9)

输出

输出一行整数，表示背包的最大价值。

样例输入 Copy 

10 
5
2 3 7 8 2
10 5 2 3 1

样例输出 Copy 

16

来源/分类

回溯法 
[提交] [状态]