大前端最新网站,面包店网站功能建设与栏目划分,室内设计公司排名前十强及作品,微博网站开发平台题干#xff1a;
描述 小Q手里有n枚硬币#xff0c;每枚硬币有一定的金额x,他想知道#xff0c;用这些硬币能组成多少种不同的金额。但是他太笨了#xff0c;自己数懵了#xff0c;你来帮帮他好不好#xff1f;
注意#xff1a;组成金额时#xff0c;每枚硬币只能用一…题干
描述 小Q手里有n枚硬币每枚硬币有一定的金额x,他想知道用这些硬币能组成多少种不同的金额。但是他太笨了自己数懵了你来帮帮他好不好
注意组成金额时每枚硬币只能用一次但可以同时使用等面值的不同硬币
输入 第一行 n,表示第二行一共有n个数字 第二行 n个数字表示不同的硬币的面值
单组输入不用担心
输出 第一行 输出 m, 表示可以组成多少种不同的金额 第二行 按照从小到大的顺序输出所有的金额。 注意每行的结尾不要有空格否则你的答案可能会被判错。
输入样例 1
2
1 2
输出样例 1
3
1 2 3输入样例 2
2
1 1
输出样例 2
2
1 2
提示
n1000, x1x200
解题报告 不难看出这是道组合数学的题目解决这类问题凑种数有两种方式背包类dp或者是母函数这里选用了装满类0-1背包来解决这道题母函数以后可以自己试试这个数据范围应该是够了
AC代码
#includebits/stdc.husing namespace std;
const int INF 0x3f3f3f3f;
int dp[5000000 5],v[5000000 5],ans[5000000 5];
int sum;
int main()
{int n;cinn;for(int i 1; in; i) scanf(%d,vi),sum v[i];dp[0]0;for(int i 1; i200000; i) dp[i] -INF;for(int i 1; in; i) {for(int j sum; jv[i]; j--) {dp[j] max(dp[j],dp[j-v[i]] v[i]);}}int cnt 0;for(int i 1; i200000; i) {if(dp[i] 0) {cnt;ans[cnt] i;}} printf(%d\n,cnt);for(int i 1; icnt; i) {printf(%d,ans[i]);if(i!cnt ) putchar( );}return 0 ;
}
//5
//100 100
//100
//100
//100
总结 没有错刚开始wa了这么多发就是因为背包写错了没加那个max、、、话说啊不到半个月没写背包你就忘这么干净了
