完全背包变形

(参考高赞回答)

  • 第i轮 dp[j]:前i种物品组合成容量恰好为j的方法数
  • 递推关系:类比完全背包(优化) dp[j]=dp[j]+dp[j-w[i]]
#include<iostream>
#include<cmath>
using namespace std;

int w[22];
int dp[1000000001];

int best(int sum,int n){
    dp[0]=1;//容量为0时,初始方法数为1
    for(int i=1;i<=sum;i++){//容量为0时,初始方法数为0(注意不是INF)
        dp[i]=0;
    }
    
    for(int i=1;i<=n;i++){
        for(int j=w[i];j<=sum;j++){//从前往后更新
             dp[j]=dp[j]+dp[j-w[i]];
            dp[j]=dp[j]%1000000000;
        }
    }
    return dp[sum];
}

int main(){
    int sum,n;
    while(scanf("%d",&sum)!=EOF){
        for(int i=1;i<=21;i++)w[i]=pow(2,i-1);
        printf("%d\n",best(sum,21));
    }
}