POJ-2229 Sumsets---完全背包变形

题目链接:

https://vjudge.net/problem/POJ-2229

题目大意:

给定一个N,只允许使用2的幂次数,问有多少种不同的方案组成N。

思路:

处理出2的幂次方的所有的数字,当做物品,每个物品次数不限,求凑出体积为N的方案数

类似完全背包,先枚举物品,再正序枚举体积,转移状态dp[i][j]表示前i件物品凑出的体积为j的方案数

dp[i][j] = dp[i - 1][j] + dp[i - 1][j - w[i]]

 1 #include<iostream>
 2 #include<vector>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cstring>
 6 #include<cstdio>
 7 #include<set>
 8 #include<map>
 9 #include<cmath>
10 #include<sstream>
11 using namespace std;
12 typedef pair<int, int> Pair;
13 typedef long long ll;
14 const int INF = 0x3f3f3f3f;
15 int T, n, m, minans;
16 const int maxn = 1e6 + 10;
17 const int mod = 1e9;
18 int dp[maxn];
19 int w[100], tot;
20 int main()
21 {
22     cin >> n;
23     for(int i = 0; (1<<i) <= n; i++)
24     {
25         w[tot++] = (1<<i);//构造出所有物品
26     }
27     //完全背包,dp[i][j]表示前i件物品凑成j体积的方案数
28     //dp[i][j] = dp[i - 1][j] + dp[i -1][j - w[i]];
29     dp[0] = 1;
30     for(int i = 0; i < tot; i++)
31     {
32         //完全背包,正序
33         for(int j = w[i]; j <= n; j++)
34             dp[j] = (dp[j] + dp[j - w[i]]) % mod;
35     }
36     cout<<dp[n]<<endl;
37     return 0;
38 }
原文地址:https://www.cnblogs.com/fzl194/p/8824214.html