PHP 网站开发 重点知识,做网站怎么选取关键词,公司网站首页怎么设置,ue4培训题目#xff1a; 题目描述 现有n个砝码#xff0c;重量分别为a1#xff0c;a2#xff0c;a3#xff0c;……#xff0c;an#xff0c;在去掉m个砝码后#xff0c;问最多能称量出多少不同的重量#xff08;不包括0#xff09;。 输入输出格式 输入格式#xff1a; 输…题目 题目描述 现有n个砝码重量分别为a1a2a3……an在去掉m个砝码后问最多能称量出多少不同的重量不包括0。 输入输出格式 输入格式 输入文件weight.in的第1行为有两个整数n和m用空格分隔 第2行有n个正整数a1a2a3……an表示每个砝码的重量。 输出格式 输出文件weight.out仅包括1个整数为最多能称量出的重量。 输入输出样例 输入样例#13 1
1 2 2 输出样例#13 说明 【样例说明】 在去掉一个重量为2的砝码后能称量出123共3种重量。 【数据规模】 对于20%的数据m0 对于50%的数据m≤1 对于50%的数据n≤10 对于100%的数据n≤20m≤4mnai≤100。 #include iostream
#include cstring
using namespace std;
int n, m, MAX 0, answer 0;
int Weight[21];
int F[20001];
bool judge[21];
int Find()//判断每一种重量是否存在因为所产生的所有的值只可能是1~maxx之间的数
{int total 0;memset(F, 0, sizeof(F));F[0] 1;for (int i 1; i n; i){if (!judge[i]){for (int j MAX; j Weight[i]; j--){F[j] F[j - Weight[i]];}}}for (int i 1; i MAX; i){if (F[i]){total;}}answer max(answer, total);
}
void Search(int counts, int pos)
{if (counts m 1){Find();}else{if (pos n){return ;//从1~n来一遍}judge[pos] true;Search(counts 1, pos 1);//某一个数字在组合的过程中只有两种可能一种是选一种是不选所以会出现两种情况故搜两次 judge[pos] false;Search(counts, pos 1);}
}
int main()
{cin n m;for (int i 1; i n; i){cin Weight[i];MAX Weight[i];//计算出总重量}if (m 0){Find();}Search(1, 1);cout answer endl;
} 转载于:https://www.cnblogs.com/ZDHYXZ/p/6857244.html
