跳至正文
题库4291
#4291

最大体积

查看题目操作

最大体积

题目描述

每个物品有一定的体积,不同的物品组合,装入背包会占用一定的总体积。假如每个物品有无限件可用,那么有些体积是永远也装不出来的。为了尽量装满背包,附中的 OIer 想要研究一下物品不能装出的最大体积。

若不能装出的体积是有限个,题目保证其中最大的不超过 2,000,000,000。若不能装出的体积不存在(如物品中含有体积 1),或有无限多个(如全部体积的最大公约数大于 1),则输出 0。

输入格式

第一行一个整数 n(n ≤ 10),表示物品的件数。第 2 到 n+1 行:每件物品的体积(1 ≤ 体积 ≤ 500)。

输出格式

一个整数 ans,表示不能用这些物品得到的最大体积。

样例

3
3
6
10
17

配图

配图

来源

蓝桥杯 算法训练