不过uim由于买了一些辅(e)辅(ro)书,口袋里只剩 m 元(m≤10000)。
餐馆虽低端,但是菜品种类不少,有 n 种(n≤100),第 i 种卖 ai 元(ai≤1000)。由于是很低端的餐馆,所以每种菜只有一份。
小A奉行“不把钱吃光不罢休”,所以他点单一定刚好把uim身上所有钱花完。他想知道有多少种点菜方法。
由于小A肚子太饿,所以最多只能等待 1 秒。
输入格式
第一行是两个数字,表示 n 和 m。
第二行起 n 个正数 ai(可以有相同的数字,每个数字均在 1000 以内)。
输出格式
一个正整数,表示点菜方案数,保证答案的范围在 int 之内。
输入输出样例
输入 #1
1 2
4 4 1 1 2 2
输出 #1
1
3
说明/提示
2020.8.29,增添一组 hack 数据 by @yummy。
思路
背包问题,考虑一个菜品选或不选两种情况,类似 0−1 背包,但是这里是计数问题。考虑动态规划解决问题,设计状态 f(i,j,0/1):f(i,j,0) 表示考虑完第 i 个物品,当前背包内价值为 j,且不选择第 i 个物品的方法数;f(i,j,1) 表示考虑完第 i 个物品,当前背包内价值为 j,且选择第 i 个物品的方法数。
类似 0−1 背包,有递推关系 f(i,j,0)=f(i−1,j,0)+f(i−1,j,1) 和 f(i,j,1)=f(i−1,j−ai,0)+f(i−1,j−ai,1);临界条件为 f(i,0,0)=1 和 f(i,0,1)=0。