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+5; typedef long long ll; using namespace std; int a[maxn],dp[200005]; int main() {int n;cin>>n;int sum=0; for(int t=1;t<=n;t++){scanf("%d",&a[t]);sum+=a[t];}for(int t=1;t<=sum;t++){dp[t]=-Inf;}dp[0]=0;for(int t=1;t<=n;t++){for(int j=sum;j>=a[t];j--){dp[j]=max(dp[j],dp[j-a[t]]+a[t]);} }int s[200005];int cnt=0;for(int t=1;t<=sum;t++){if(dp[t]>=0){s[cnt++]=dp[t];}}cout<<cnt<<endl;for(int t=0;t<cnt;t++){if(t==0){printf("%d",s[t]);}else{printf(" %d",s[t]);}}return 0; }

?

轉載于:https://www.cnblogs.com/Staceyacm/p/10801119.html

總結

以上是生活随笔為你收集整理的qdu-凑数题(01背包)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。