AW278 数字组合（0/1背包）

题目地址

---

状态设计：

• f[i]：和为i时的总选择方案数.

易错点：

• 初始值f[0]应设为1.
• 第二层循环（背包体积）时的循环条件应设为j>=a[i].

---

#include<cstdio>
#include<iostream>
using namespace std;
const int MAXN=1e3;
int a[MAXN],f[MAXN];
int main(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
	}
	f[0]=1;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=a[i];j--){//
			f[j]+=f[j-a[i]];
		}
	}
	printf("%d
",f[m]);
	return 0;
}