专栏文章

题解：B4177 [BCSP-X 2024 6 月初中组] 尽量接近

kkkksb_04
B4177题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miogdpdd
此快照首次捕获于
2025/12/02 18:46
3 个月前
此快照最后确认于
2025/12/02 18:46
3 个月前
查看原文

B4177题解

分析：

01背包，有n个物品（数字），每个数字重量为自己，背包容量为k。不过注意一点：不是越大越好，而是越接近k越好。 dp[i][j]表示拿第i个数字背包空间为j时的最接近k的值

写法：

用函数判断是否更新dp的值
CPP
bool f(int x,int y){
	int ta=abs(k-x),tb=abs(k-y);
	if(ta!=tb){
		return tb<ta;
	}
	return y<x;
}
然后完成代码
CPP
bool f(int x,int y){
	int ta=abs(k-x),tb=abs(k-y);
	if(ta!=tb){
		return tb<ta;
	}
	return y<x;
}
signed main(){
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
	}
	for(int i=1;i<=n;i++){
		for(int j=k;j>=a[i];j--){
			if(f(dp[j],dp[j-a[i]]+a[i])){
				dp[j]=dp[j-a[i]]+a[i];
			}
		}
	}
	cout<<dp[k];
交上后就会惊奇的发现 80pts!!!
反例：2 10 8 11
这个程序输出的是8

哦!

原来比k大的数没有在dp数组里
那就简单了
将大小k改成所有数字的和sum就可以啦

AC代码如下

CPP
bool f(int x,int y){
	int ta=abs(k-x),tb=abs(k-y);
	if(ta!=tb)	return tb<ta;
	return y<x;
}
int fx(int x,int y){
	int ta=abs(k-x),tb=abs(k-y);
	if(ta<tb)	return x;
	if(tb<ta)   return y;
	if(x<y)  return x;
	return y;
}
int main()
    cin>>n>>k;
    for(int i=1;i<=n;i++){
    	cin>>a[i];
    	sum+=a[i];
	}
	for(int i=1;i<=n;i++)
		for(int j=max(sum,k);j>=a[i];j--)
			if(f(dp[j],dp[j-a[i]]+a[i]))
				dp[j]=dp[j-a[i]]+a[i];
	ans=-1;
	for(int i=0;i<=sum;i++){
		ans=fx(ans,dp[i]);
	}
	cout<<ans;
os:本蒟蒻第一篇题解，求管理大大通过

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...