网站群建设,厦门市住房建设网站,制作公司网页价钱,网站项目建设措施题目描述
给你n个物品#xff0c;每种物品有一个体积Vi#xff0c;求从中取出若干物品能够组成的不同的体积和有多少种可能。例如#xff0c;n3#xff0c;Vi(1,3,4)#xff0c;那么输出6。6种不同体积和具体为1,3,4,5,7,8。
输入
第一行一个整数n#xff1b; 第二行…题目描述
给你n个物品每种物品有一个体积Vi求从中取出若干物品能够组成的不同的体积和有多少种可能。例如n3Vi(1,3,4)那么输出6。6种不同体积和具体为1,3,4,5,7,8。
输入
第一行一个整数n 第二行n个整数表示Vi每两个数之间用一个空格隔开。
输出
一行一个数表示不同的体积和有多少种可能
样例输入 Copy
3
1 3 4样例输出 Copy
6提示
对于30%的数据满足n≤5,1≤Vi≤10; 对于60%的数据满足n≤10,1≤Vi≤20; 对于100%的数据满足n≤20,1≤Vi≤50; 以下提供两种思路。 两种思路的内存均为2024KB。 第一种的时间为36ms第二种的时间为12ms。 第二种的代码更为简洁且高效。 但是为了练dfs还是先考虑了dfs的思路。 思路一dfs #include bits/stdc.h
using namespace std;
int n, cnt, v[50];
bool st[1010];
void dfs(int depth, int sum)
{if (depth n){st[sum] true;return;}dfs(depth 1, sum v[depth]);dfs(depth 1, sum);
}
int main()
{cin n;for (int i 1; i n; i) cin v[i];dfs(1, 0);for (int i 1; i 1000; i)if (st[i]) cnt;cout cnt \n;return 0;
} 思路二妙 #include bits/stdc.h
using namespace std;
int n, cnt, v, i;
bool st[1010];
int main()
{cin n;st[0] 1;while (n--){cin v;for (i 1005; i v; i--)if (st[i - v]) st[i] 1;}for (i 1; i 1000; i)if (st[i]) cnt;cout cnt \n;return 0;
} 初步接触dfs写了一大堆结果超时了问老师才发现自己写麻烦了
