No.2364 Knapsack Problem
タグ : / 解いたユーザー数 133
作問者 :
logx
/ テスター :
Kak1_n0_tane
Problem Statement
Pina has come to a shopping street with a knapsack of capacity $W$. There are $N$ items for sale on the shopping street, and Pina can use $M$ types of magic.
The knapsack has a weight $w$ and a value $v$, determined by the items in it and so on. Initially, $w=0,v=0$.
As long as $0 \leq w \leq W$ holds before and after each operation, Pina can perform the following $N+M$ operations in any order. (Each operation can be performed at most $1$ time. Some operations may be left unperformed.)
Maximize the value $v$.
- Choose $i$ such that $1 \leq i \leq N$ and buy the $i$-th item.
The value of $w$ increases by $A_i$, and the value of $v$ increases by $B_i$. - Choose $i$ such that $1 \leq i \leq M$ and use the $i$-th magic.
The value of $w$ decreases by $C_i$, and the value of $v$ decreases by $D_i$.
Input
$N\ M\ W$ $A_1\ \cdots\ A_N$ $B_1\ \cdots\ B_N$ $C_1\ \cdots\ C_M$ $D_1\ \cdots\ D_M$
- $1 \leq N \leq 7$
- $1 \leq M \leq 7$
- $1 \leq W \leq 500$
- $1 \leq A_i \leq W$
- $1 \leq B_i \leq 10^8$
- $1 \leq C_i \leq W$
- $1 \leq D_i \leq 10^8$
- All inputs are integers.
Output
Output the maximum possible value of $v$. Print a newline at the end.
Sample
Sample 1
Input
2 2 30 5 20 10 15 10 5 20 5
Output
25
You can buy the $2$ items without using any magic.
Sample 2
Input
2 2 30 15 20 10 15 10 5 20 5
Output
20
The following procedure achieves $v=20$.
- Buy item $1$.
- Use magic $2$.
- Buy item $2$.
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。