【u204】高级砝码称重
2024-10-01 21:54:42
Time Limit: 1 second
Memory Limit: 128 MB
【问题描述】
现有n个砝码,重量分别为a1,a2,a3,……,an,在去掉m个砝码后,问最多能称量出多少不同的重量(不包括0)。
【输入格式】
输入文件weight.in的第1行为有两个整数n和m,用空格分隔 第2行有n个正整数a1,a2,a3,……,an,表示每个砝码的重量。
【输出格式】
输出文件weight.out仅包括1个整数,为最多能称量出的重量。
【数据规模】
对于20%的数据,m=0; 对于50%的数据,m≤1; 对于50%的数据,n≤10; 对于100%的数据,n≤20,m≤4,m<n,ai≤100。
Sample Input1
3 1
1 2 2
Sample Output1
3
【样例说明】
在去掉一个重量为2的砝码后,能称量出1,2,3共3种重量。
【题解】
这是一个0/1背包+搜索的问题。
先选出m个物品,把他们"去掉“,然后对剩余的物品,进行0/1背包就可以了。
ai<=100,n<=20,则枚举的最大重量为2000;
用一个boolean型的bo数组来表示某一个重量是否能达到。
if (can[j-w[i]])
can[j] = true;
最后统计一下重量的种数就可以了。
【代码】
#include <cstdio>
#include <cstring> int 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;j>=w[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 = x+1;i <= n;i++) //从x+1开始表示是一个组合问题,从n个中选出m个。
if (bo[i])
{
bo[i] = false;
select(i,num+1);
bo[i] = true;
}
} void get_ans()
{
memset(bo,true,sizeof(bo));
select(0,0);//从0开始,可以包括m==0的情况。
} 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;
}
最新文章
- vs2010 打开 vs2012 的解决方案
- 在Linux下安装和使用MySQL
- 实测可用的免费STUN服务器!
- 转:最简单的基于 DirectShow 的视频播放器
- 常用HTML正则
- electron小例子
- hdu 4712 Hamming Distance(随机数法)
- BBOSS框架使用jquery方式传參到后台的时候,要注意的事项
- 两个android程序间的相互调用(apk互调)
- Postman newman
- Java简单工厂模式以及来自lambda的优化
- 20145237《Java程序设计》第一周学习总结
- vue添加页面键盘事件
- TCP传输
- Minesweeper
- [hdu5215][Cycle]
- vcf文件去除非变异的基因型(use GATK exclude nonvariant in vcf format,0|0,0/0)
- 改变FileUpload文件上传控件的显示方式,确认后上传
- Python 基于时间的进程通信
- [docker]使用quaaga实现(rip ospf)实现主机间容器互通