【无码专区12】子集和（背包dp）

此题已自我实现，但仍归于无码专区

本题在考场上就过了，所以难度并不高，发现性质即可。

problem

有 $n$ 个正整数 $a_1,a_2,...,a_n$，他们的和为 $m$。你想对于其每一个子集 $S$，求出他们的和。

给定 $2^n$ 个 $[0,m]$ 之间的和，其中数字 $i$ 出现了 $b_i$ 次。

求还原 $a$，数据保证有唯一解。

$n\le 50,m\le 10000,1s,128MB$

my idea

首先就能知道 $b_0,b_m$ 一定是 $1$。

马上就发现最小的 $a_i$ 是没有能被其他数组合出来的情况的，因为他们全是正数！

所以最小的 $b_i\ne 0$ 的 $i$，就意味着 $a$ 中原来有 $b_i$ 个 $i$。

然后考虑第二小的 $b_j\ne 0$ 的 $j$，会注意到有可能 $b_i$ 个 $i$ 可能会组合出 $j$。

减去这些组合就是 $a$ 中原本有 $b_j^{\prime }$ 个 $j$。

发现这就是个背包 $dp$ 的过程。

容量 $m$，但最多只会背包 $n$ 次。

所以跑得很快。

solution

与我的想法相同。

每次找到子集中最小的元素，也就是最小的 $b_i$ 不等于 $0$ 的 $i$，然后从背包里删去即可。

删除就是可以理解成逆向执行一下背包中加入元素 $x$ 的操作，也就是从小到大，执行 $b_i-=b_{i-x}$。

code

#include <bits/stdc++.h> using namespace std; #define maxn 55 #define maxm 10005 #define int long long int n, m, cnt; int b[maxm], a[maxn], f[maxm]; int c[maxn][maxn];signed main() {freopen( "subset.in", "r", stdin );freopen( "subset.out", "w", stdout );scanf( "%lld %lld", &n, &m );for( int i = 0;i <= n;i ++ ) {c[i][0] = c[i][i] = 1;for( int j = 1;j < i;j ++ )c[i][j] = c[i - 1][j - 1] + c[i - 1][j];}for( int i = 0;i <= m;i ++ ) scanf( "%lld", &b[i] );f[0] = 1;for( int i = 1;i <= m;i ++ ) {b[i] -= f[i];if( ! b[i] ) continue;for( int j = 1;j <= b[i];j ++ ) a[++ cnt] = i;for( int j = m;j;j -- ) {for( int k = 1;k <= b[i];k ++ )if( j < k * i ) break;else f[j] += f[j - k * i] * c[b[i]][k];}}for( int i = 1;i <= n;i ++ ) printf( "%lld ", a[i] );return 0; }

总结

以上是生活随笔为你收集整理的【无码专区12】子集和（背包dp）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。