题解 | #CSL分苹果#

非常板子的DP背包问题，不过板子也有板子的好处，可以让修补骑士快速上手熟悉某个知识点的写法

在这里就说两个我犯的错吧

1：我们都知道，对于每一个元素选或者不选，我们是从后向前的（防止多选），但是我们写循环要写成for(int y = allwei/2;y >= weight[r];y--)而不是>=0，原因是因为我们使用了max来记录最大值，对于装不下的理所应当为0，但是可能就变成了dp[y - weight[r]] + weight[r])，这里dp是0，但是weight不是，会造成错误的结果。所以说对于根本装不下的r，我们是需要显示说明的

（如果剩余空间根本装不下，那当然是保持不变了，刚好还契合了一维容器的特性）

2：修补骑士一开始以为单位价值为1，结果发现还不如原汤化原食，价值也变为weight，到时候直接一并输出了

AC代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

signed main() 
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);

    int n;
    
    cin>>n;
    
    vector<int> weight(n,0);
    
    for(int r = 0;r < n;r++)
    {
        cin>>weight[r];
    }
    
    int allwei = accumulate(weight.begin(),weight.end(),0);
    //哇，又有没用的新关键词
    
    vector<int> dp((allwei/2) + 1,0);
    
    for(int r = 0;r < n;r++)
    {
        for(int y = allwei/2;y >= weight[r];y--)
        {
            dp[y] = max(dp[y],dp[y - weight[r]] + weight[r]);
        }
    }
    
    cout<<dp[allwei/2]<<" "<<allwei - dp[allwei/2]<<endl;
    
    return 0;
}