方法一：
$\mathrm{f[x]}$ 表示所有物品凑成体积为 $\mathrm{x}$ 的方案数.
$\mathrm{g[x][j]}$ 表示不用 $\mathrm{x}$ 物品组成体积为 $\mathrm{j}$ 的方案数.
然后 $\mathrm{g}$ 数组可以用 $\mathrm{f,g}$ 容斥搞一波.
时间复杂度为 $\mathrm{O(nm)}$.
方法二：
主要介绍一下分治解决 01 背包的方法.
不难发现暴力算的话很多部分是重复的，而用线段树可以简化操作.
令 $\mathrm{solve(l,r,dep)}$ 表示当前 $[l,r]$ 的物品没有加入，其他物品都加入的背包.
每次进入左边分治前把右子树算进去.
每次进入右子树前撤销原本的右子树并加入左子树.
时间复杂度： $O(nm \log n)$.
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
#define N 2005
#define ll long long
#define pb push_back
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
const int mod=10;
int n,m, v[N], f[20][N];
void solve(int l, int r, int dep) {
if(l == r) {
for(int i=1;i<=m;++i) {
printf("%d",f[dep-1][i]);
}
printf("\n");
return ;
}
int mid=(l+r)>>1;
// 复制.
for(int i=0;i<=m;++i) f[dep][i]=f[dep-1][i];
for(int i=mid+1;i<=r;++i) {
for(int j=m;j>=v[i];--j) {
(f[dep][j]+=f[dep][j-v[i]])%=mod;
}
}
solve(l, mid, dep+1);
for(int i=0;i<=m;++i) f[dep][i]=f[dep-1][i];
for(int i=l;i<=mid;++i) {
for(int j=m;j>=v[i];--j)
(f[dep][j]+=f[dep][j-v[i]])%=mod;
}
solve(mid+1,r,dep+1);
}
int main() {
// setIO("input");
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i) {
scanf("%d",&v[i]);
}
f[0][0]=1;
solve(1, n, 1);
return 0;
}
原文：https://www.cnblogs.com/brady12/p/15270538.html