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

违规用户名^2vfX-sg · 2025-08-08 16:55:29 · 题解

B4177题解

分析：

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

写法：

用函数判断是否更新dp的值

bool f(int x,int y){
    int ta=abs(k-x),tb=abs(k-y);
    if(ta!=tb){
        return tb<ta;
    }
    return y<x;
}

然后完成代码

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代码如下

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:本蒟蒻第一篇题解，求管理大大通过