涉及知识点：

• 01背包

solution：

• \(题意非常简单，做法也非常简单\)
• \(一道裸的01背包问题\)
• \(01背包的简单理解：\)
• \(给定n种物品和一个容量为w的背包，物品i的重量是wi，其价值为vi\)
• \(应该如何选择装入背包的物品，使得装入背包中的物品的总价值最大？\)
• \(那么本题，设W = 所有苹果的重量之和，假定一个大小为\frac{W}{2}的背包\)
• \(问题简化成往大小为\frac{W}{2}的背包塞苹果，使得总重量最大\)

std:

#include <bits/stdc++.h>
using namespace std;
#define ll long long 
const int maxn = 10005;
int dp[maxn],w[maxn];
int main(){
    int n,cnt = 0;
    cin>>n;
    for(int i=1;i<=n;i++)
        cin>>w[i] , cnt += w[i];
    for(int i=1;i<=n;i++){
        for(int j=cnt/2;j>=w[i];j--){
            dp[j] = max(dp[j] , dp[j - w[i]] + w[i]);
        }
    }
    cout<<dp[cnt/2]<<" "<<cnt - dp[cnt/2]<<endl;
    return 0;
}

4.30 每日一题题解

原文：https://www.cnblogs.com/QFNU-ACM/p/12807124.html