問題一覧 > 通常問題

No.2364 Knapsack Problem

レベル : / AI推定難易度 : 1000 / 実行時間制限 : 1ケース 3.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 133
作問者 : logx / テスター : shobonvip Kak1_n0_tane Carpenters-Cat comavius
お気に入りにしたユーザー ProblemId : 6669 / 自分の提出
問題文最終更新日: 2023-06-30 17:51:09
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 395 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。