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

_DATA_X_ · 2025-06-11 11:29:12 · 题解

B4177 题解

主要思路：

01 背包求解。

• 定义一个二维数组 f，其中 f_{i,j} 定义为前 i 项的和是否能构成 j。
• 双层循环遍历，判断所有可能构成的和，默认当前项为 f_{i-1,j}，如果当前的 j\ge a_{i-1}，则运用或运算更新当前值。
• 综上所述，状态转移方程为： f_{i,j}=f_{i,j}\lor f_{i-1,j-a_i-1}

  代码实现：

码风很烂，dalao 勿喷。

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,k,mi=INT_MAX,ans=0;//n，k为题目的n，k，mi为最小差值，ans为总和
int a[60];
signed main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>k;
    for(int i=0;i<n;i++){
        cin>>a[i];
        ans+=a[i];//求总和
    }//输入
    bool f[60][ans+1];//dp数组
    memset(f,0,sizeof(f));//重置
    f[0][0]=1;//前0项的和能构成0
    for(int i=1;i<=n;i++){
        for(int j=0;j<=ans;j++){
            f[i][j]=f[i-1][j];
            if(j>=a[i-1]){
                f[i][j]=(f[i][j]||f[i-1][j-a[i-1]]);
            }
        }
    }//状态转移方程   
    int cnt=0;//存最终结果
    for(int i=0;i<=ans;i++){
        if(f[n][i]==1){
            if(abs(i-k)<mi||(abs(i-k)==mi&&i<cnt)){
                mi=abs(i-k);//存下当前最小差值
                cnt=i;//存下当前最小值
            }
        }
    }
    cout<<cnt;//输出结果
    return 0;
}