【POJ - 2229】Sumsets（完全背包）

sky-stars 2019-08-11 原文

【POJ – 2229】Sumsets（完全背包）

Sumsets

直接翻译了

Descriptions

Farmer John 让奶牛们找一些数加起来等于一个给出的数N。但是奶牛们只会用2的整数幂。下面是凑出7的方式

1) 1+1+1+1+1+1+1
2) 1+1+1+1+1+2
3) 1+1+1+2+2
4) 1+1+1+4
5) 1+2+2+2
6) 1+2+4

帮助FJ找到 N的分配数 (1 <= N <= 1,000,000).

Input

Output

排列方式总数。由于这个数可能很大，只需要保留最后9位

Sample Input

Sample Output

Hint

打表的会被系统自动识别判为WA

题目链接

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

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

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

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

1<<i 相当于 2ⁱ

AC代码

#include <iostream>
#include <cstdio>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <deque>
#include <vector>
#include <queue>
#include <string>
#include <cstring>
#include <map>
#include <stack>
#include <set>
#include <sstream>
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define Mod 1000000007
#define eps 1e-6
#define ll long long
#define INF 0x3f3f3f3f
#define MEM(x,y) memset(x,y,sizeof(x))
#define Maxn 1000005
using namespace std;
int n;
int w[Maxn];
int cnt=0;
int dp[Maxn];
int main()
{
    scanf("%d",&n);
    for(int i=0;(1<<i)<=n;i++)//构造所有物品
        w[cnt++]=(1<<i);
    dp[0]=1;
    for(int i=0;i<cnt;i++)
        for(int j=w[i];j<=n;j++)
            dp[j]=(dp[j]+dp[j-w[i]])%1000000000;//取余
    printf("%d\n",dp[n]);
    return 0;
}