AT_k4pc_e.はじめての動的計画法(Easy Dynamic Programming)

狐のジャップル正在为编程竞赛平台 K4PC 出题。今天，他想出了这样一个问题。

问题描述

在超市的生鲜食品摊上，有 $ N $ 根黄瓜待售。结账时，如果你购买的黄瓜总重量不超过 $ W $，就能够获得生产者三木先生的亲笔签名。

健介非常喜爱三木先生种植的黄瓜，因此他想尽可能多地收集到这些签名。请你帮忙计算一下，有多少种购买组合可以使他获得签名。

任务

有 $ N $ 个物品，每个物品的重量都是一个正整数 $ a_i $ ($ 1 \leq i \leq N $)。

求所有重量和不超过 $ W $ 的物品组合的数量。

约束条件

• $ 1 \leq N \leq 1000 $。
• $ 1 \leq W \leq 1000 $。
• $ 1 \leq a_i \leq 1000 $。

输入格式

输入包括一行：

$ N $ $ W $ $ a_1 $ $ a_2 $ … $ a_N $

输出格式

输出一个整数，表示满足条件的购买组合数量。

输入样例 1

4 4
1
1
2
3

输出样例 1

11

满足条件的组合包括：空集 $ {} $、单个黄瓜 $\{a_1\}$、$\{a_2\}$、$\{a_3\}$、$\{a_4\}$，以及多个黄瓜组合如 $\{a_1, a_2\}$、$\{a_1, a_3\}$、$\{a_2, a_3\}$、$\{a_1, a_4\}$、$\{a_2, a_4\}$、$\{a_1, a_2, a_3\}$。

额外任务

找到一个输入，使得问题 " Do use Dynamic Programming " 的输出为给定的整数 $ x $。

输入约束条件

只需保证输出满足以下条件：

• $ 1 \leq x \leq 10^{18} $。

提前保证在上述条件下，问题有解。（13:51 更新）

此外，为部分分问题数据集，要求输出 $ x \leq 1000 $。

本翻译由 AI 自动生成