qdu-凑数题(01背包)

Description

小Q手里有n(n<=1000) 个硬币，每枚硬币有一定的金额（200=>x>=1）他想知道，用这些硬币（每枚硬币只能用一次，但可能会有等面值的用两次）能组成多少种不同的金额？

Input

第一行 n,表示第二行一共有n个数字，第二行表示n个数字

Output

第一行输出 m, 表示可以组成多少种不同的金额第二行按照从小到大的顺序输出所有的金额。注意，每行的结尾，不要有空格，否则你的答案可能会被判错。

Sample Input 1

2

1 2

Sample Output 1

3

1 2 3

Sample Input 2

2

1 1

Sample Output 2

2

1 2

01背包的未装满的情况
代码：

#include<cstdio>

#include<iostream>

#include<cstring>

#include<algorithm>

#include<queue>

#include<stack>

#include<set>

#include<vector>

#include<map>

#include<cmath>

#define Inf 0x3f3f3f3f

const int maxn=1e5+;

typedef long long ll;

using namespace std;

int a[maxn],dp[];

int main()

{

   int n;

   cin>>n;

   int sum=;

   for(int t=;t<=n;t++)

   {

       scanf("%d",&a[t]);

       sum+=a[t];

   }

   for(int t=;t<=sum;t++)

   {

       dp[t]=-Inf;

   }

   dp[]=;

   for(int t=;t<=n;t++)

   {

        for(int j=sum;j>=a[t];j--)

     {

         dp[j]=max(dp[j],dp[j-a[t]]+a[t]);

     }

   }

   int s[];

   int cnt=;

   for(int t=;t<=sum;t++)

   {

       if(dp[t]>=)

       {

           s[cnt++]=dp[t];

    }

   }

   cout<<cnt<<endl;

   for(int t=;t<cnt;t++)

   {

       if(t==)

       {

           printf("%d",s[t]);

    }

    else

    {

        printf(" %d",s[t]);

    }

   }

   return ;

}

巴特西

qdu-凑数题(01背包)

最新文章

热门文章