深度优先搜索

P970 坤坤爱下蛋 2023南阳理工学院第四届省内高校新生程序设计大赛-CSDN博客 这里为什么发不出代码

• [ ] 这是一道类似于“目标和”的0-1背包问题，对于第i个鸡蛋和坤蛋，只有两种情况，要么鸡蛋放在A，坤蛋放在B，要么鸡蛋放在B，坤蛋放在A，思考一下这两种情况会怎么影响答案，总和之差最小实际上跟两蛋之差有关，两蛋之差要么是A-B，要么是B-A，我们不妨对两蛋之差取绝对值，然后问题就变为了在一堆数(两蛋之差绝对值)中添加-或+号，令其相加和最接近0，因此问题继续优化变为从一堆数中选择一些数，让他们的和尽可能接近sum/2(负数和正数越接近,sum为两蛋差绝对值的和)，就变为了标准的0-1背包问题。

1. 定义dp[i][j]为选择到第i个物品时，能否有一个子集和等于j；
2. 对于第i个数来说，我们有选和不选两种情况，对应的状态转移方程如下:

不选：dp[i][j]=dp[i-1][j] 选:dp[i][j]=max(dp[i-1][j],dp[i-1][j-diff[i-1]]) 有一个满足即满足，所以取max； 初始化dp[i][0]为true，即不选任何数，能达到目标为0; 最后从sum/2往前遍历，找最接近sum/2的数然后相减即为答案；

#include<bits/stdc++.h>
using namespace std;
int n,egg[205],kgg[205],sum=0,maxv=0,diff[205];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)cin>>egg[i];
    for(int i=0;i<n;i++){
        cin>>kgg[i];
        diff[i]=abs(egg[i]-kgg[i]);//两蛋的差值绝对值 
        sum+=diff[i];
    }
    int target=sum/2;//目标值 
    //动态规划数组 
    vector<vector<bool>> dp(n + 1, vector<bool>(target + 1));
    for (int i = 0; i <= n; ++i) {
        dp[i][0] = 1;
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= target; ++j) {
        	//不选 
            dp[i][j] = dp[i - 1][j];
            //选 
            if (j >= diff[i - 1]) {
                dp[i][j] = max(dp[i][j],dp[i - 1][j - diff[i - 1]]);
            }
        }
    }
    //从后往前遍历找最接近target的值 
    for(int i=target;i>=0;i--){
        if(dp[n][i]){
            maxv=i;
            break;
        }
    }
    //相减即为答案 
    cout<<sum-2*maxv;
	return 0;
}

时间复杂度O(sum*n)

空间复杂度O(sum*n)

一维数组实现动态规划: 因为每次只用到上一个状态，所以我们可以去掉一个维度

#include<bits/stdc++.h>
using namespace std;
int n,egg[205],kgg[205],sum=0,maxv=0,diff[205];
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
    cin>>n;
    for(int i=0;i<n;i++)cin>>egg[i];
    for(int i=0;i<n;i++){
        cin>>kgg[i];
        diff[i]=abs(egg[i]-kgg[i]);//两蛋的差值绝对值 
        sum+=diff[i];
    }
    int target=sum/2;//目标值 
    //动态规划数组 
    vector<bool>dp(target + 1);
    dp[0]=1;
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= target; ++j) {
            if (j >= diff[i - 1]) {
                dp[j] = max(dp[j],dp[j - diff[i - 1]]);
            }
        }
    }
    //从后往前遍历找最接近target的值 
    for(int i=target;i>=0;i--){
        if(dp[i]){
            maxv=i;
            break;
        }
    }
    //相减即为答案 
    cout<<sum-2*maxv;
	return 0;
}

当然也有两个数组实现动态规划的，我就不写了(绝对不是因为懒👀️ ) 时间复杂度O(sum*n) 空间复杂度O(max(n,sum))