深圳高端做网站,国内公关公司,网站开发需要人员,活动网站怎么建设Time Limit: 1 second Memory Limit: 128 MB 【问题描述】 现有n个砝码#xff0c;重量分别为a1#xff0c;a2#xff0c;a3#xff0c;……#xff0c;an#xff0c;在去掉m个砝码后#xff0c;问最多能称量出多少不同的重量#xff08;不包括0#xff09;。 【输入… Time Limit: 1 second Memory Limit: 128 MB 【问题描述】 现有n个砝码重量分别为a1a2a3……an在去掉m个砝码后问最多能称量出多少不同的重量不包括0。 【输入格式】 输入文件weight.in的第1行为有两个整数n和m用空格分隔 第2行有n个正整数a1a2a3……an表示每个砝码的重量。 【输出格式】 输出文件weight.out仅包括1个整数为最多能称量出的重量。 【数据规模】 对于20%的数据m0 对于50%的数据m≤1 对于50%的数据n≤10 对于100%的数据n≤20m≤4mnai≤100。 Sample Input1 3 1
1 2 2 Sample Output1 3 【样例说明】 在去掉一个重量为2的砝码后能称量出123共3种重量。 【题解】 这是一个0/1背包搜索的问题。 先选出m个物品把他们去掉“然后对剩余的物品进行0/1背包就可以了。 ai100,n20则枚举的最大重量为2000; 用一个boolean型的bo数组来表示某一个重量是否能达到。 if (can[j-w[i]]) can[j] true; 最后统计一下重量的种数就可以了。 【代码】 #include cstdio
#include cstringint n,m,w[21],ma 0;
bool bo[21],can[2001]; //bo用来表示哪些砝码可以用can则表示哪些重量可以由砝码称出 void input_data()
{scanf(%d%d,n,m);for (int i 1;i n;i)scanf(%d,w[i]);
}void select(int x,int num) //表示当前枚举到了第x个砝码去掉的砝码数量为num
{if (num m) //如果去掉的砝码数量达到了要求则进行一次0/1背包求出能到达的重量 {memset(can,false,sizeof(can));can[0] true;for (int i 1;i n;i)if (bo[i])for (int j 2000;jw[i];j--) //0/1背包是逆序更新的。 if (can[j-w[i]])can[j] true;int xx 0;for (int j 1 ;j 2000;j)if (can[j]) //统计能够到达的重量数目 xx;if (xx ma)ma xx;return; }for (int i x1;i n;i) //从x1开始表示是一个组合问题,从n个中选出m个。 if (bo[i]){bo[i] false;select(i,num1);bo[i] true; }
}void get_ans()
{memset(bo,true,sizeof(bo));select(0,0);//从0开始可以包括m0的情况。
}void output_ans()
{printf(%d\n,ma);
}int main()
{freopen(stronger.in,r,stdin);freopen(stronger.out,w,stdout);input_data();get_ans();output_ans();fclose(stdin);fclose(stdout);return 0;
} 转载于:https://www.cnblogs.com/AWCXV/p/7632341.html
