Problem
Gift 【问题描述】 人生赢家老王在网上认识了一个妹纸,然后妹纸的生日到了，为了表示自己的心意，他决定送她礼物。可是她喜爱的东西特别多，然而他的钱数有限，因此他想知道当他花一定钱数后剩余钱数无法再购买任何一件剩余物品(每种物品他最多买一个)时有多少种方案，两种方案不同，当且仅当两种方案中至少有一件品不同，可是由于他忙着准备泡下一个妹纸(chi)，因此麻烦聪明的你帮帮忙。
【输入格式】 输入第一行n和m，n表示妹纸喜欢的礼物数目，m表示现有的钱数，第二行n个数，表示n个物品的价格。
【输出格式】 输出一行一个数表示方案数目，答案对1000000007取模。
【样例输入1】 gift.in 6 25 8 9 8 7 16 5 【样例输出1】 gift.out 15 【数据范围】 30%的数据: 0<=n<=100 0<=m<=500 100%的数据:0<=n<=1000 0<=m<=1000 注意：所有物品价格均小于m
Solution
这个题最重要的是理解f[][]的含义：f[i][j]表示对n~i的物品做背包之后，剩余容量为j的方案数那么首先对物品的价格从小到大排序，排序的目的放在后面s[i]表示从1到i的前缀和DP是倒着循环的，从价格高的物品开始，即
f[i][j]+=f[i+1][j+v[i]]
，初值为
f[n+1][m]=1
，具体意义和01背包相同更新答案的时候，可以假设前i-1种物品一共花费了X=
∑i−1k=1ak
元，分配给前i-1种物品的容量为X时的方案数一定为1，而求的是买不到时的方案数，因此分配给第i个物品的钱数c应该满足
0<=c<ai
，而j的范围是
s[i−1]<=j<s[i]
（同样注意是”<=”和”<”），当然s[i]>m的情况特殊判断一下
Code
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#define LL long long
using namespace std;
const int N=
1010;
const int mod=
1e9+
7;
int n,m;
int a[N];
LL s[N];
LL f[N][N];
LL ans;
int main(){
scanf(
"%d%d",&n,&m);
for(
int i=
1;i<=n;++i)
scanf(
"%d",&a[i]);
sort(a+
1,a+
1+n);
for(
int i=
1;i<=n;++i) s[i]=s[i-
1]+a[i];
if(s[n]<m){
cout<<
1;
return 0;
}
f[n+
1][m]=
1;
for(
int i=n;i>=
1;--i){
int k=min((LL)m+
1,s[i]);
for(
int j=s[i-
1];j<k;++j) (ans+=f[i+
1][j])%=mod;
for(
int j=m;j>=
0;--j){
if(j+a[i]<=m) (f[i][j]+=f[i+
1][j+a[i]])%=mod;
f[i][j]+=f[i+
1][j];
}
}
cout<<ans;
return 0;
}
