首页 > 试题广场 >

Knapsack Problem

[编程题]Knapsack Problem
  • 热度指数:9 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 128M,其他语言256M
  • 算法知识视频讲解
Today HH becomes a shopper, and he wants to buy a lot.
HH has a bag that can carry at most w kilograms things in total, and he has d dollars.
Now he wants to buy n items,the ith item weights wi kilogram and costs ci dollars.
HHis not good at math so he asks you to tell him whether he can buy all the things and carry them with the bag.

输入描述:
The first line contains an positive integer T(1≤T≤10), represents there are T test cases. 
For each test case: 
The first line contains three positive integers n,w,d(1≤n≤100,1≤w≤100,1≤d≤100) - the number of items HH wants to buy, the max weight that his bag can carry, and the money he has. 
The second line contains n integers w1,w2…wn(1≤wi≤100). The third line contains n integers c1,c2…cn(1≤ci≤100).


输出描述:
For each test case, output one line "YES" (without quotes) if HH is possible to buy all the items and carry them in his bag, and "NO" (without quotes) otherwise.
示例1

输入

2
4 12 17
1 2 4 5
5 4 6 2
4 11 17
1 2 4 5
5 4 6 2

输出

YES
NO

说明

In the first example all the items cost 17 dollars in total and weight 12 kilograms in total, HH has enough money and his bag can carry 12 kilogram things.

这道题你会答吗?花几分钟告诉大家答案吧!