| # | Problem | Pass Rate (passed user / total user) |
|---|---|---|
| 12700 | 電機系 - 資料結構上機考-0 20200322 |
|
Description
- You are a theif sneaking into a house that contains N-items.
- Each item contains its own value(Vi) and weight(Wi). Your target is to steal at least K values.
- Since you are too lazy to hold too many items, so you want to take as light as possible. What is the lightest weight you need carry out from this house with at least K value?
- (ps: the sum of value you steal cannot be less then K)
- You can try to use recursive function to get whether each item is taken or not. For example:
Function getval()
{
if(terminal condition) return
return(getval(take the item),getval(not take the item))
}
Input
- The first line contains two integers N(the number of items in the house) and K(how much value you need to steel).
- Each of the following N lines contains two integers Vi and Wi, which describe the value and weight of i-th item, respectively.
Output
- Print the less weight the thief need to carry.
- P.S. You don’t need to print newline in the end!