经典0-1背包问题

题目简述：

n个牛牛吃m个糖果，每个牛牛吃ai个，k对牛牛绑定必须一起吃或不吃，每个牛牛只会出现在一对绑定中（不会重婚） 求能够吃到糖果的牛牛的最大数量。

很显然，我们把配对了的两只牛牛看作一个权值为2的物品，所需容积为二者之和；把单身的牛牛看作权值为1的物品，所需容积就是其本身所需。 那么，这就是个典型的 “0-1背包问题”。

算法分析：

0-1背包问题： n个物品，每个物品的权值为val[i]，所需容量为volume[i]，背包容积为m。每个物品要么装要么不装，求背包中物品权值总和的最大值。

核心代码就两个for循环：

for (int i = 0; i < n; i++) {
	for (int j = m; j >= volume[i]; j--) {
    	dp[j] = max(dp[j], dp[j - volume[i]] + val[i]);
    }
}
return dp[m];

解释一下为什么要从后往前更新，因为每次更新时需要借助 j 值更小的更新前的记录，即 dp_after[j] = max(dp_before[j], dp_before[j - volume[i]] + val[i])。

所以，若从前往后更新，则右边的 dp_before[j - volume[i]] + val[i]) 会变成dp_after[j - volume[i]] + val[i])，因为更新 j 的时候 j-volume[i] 已经更新过了。

反之，若从后往前更新，则更新 j 的时候 j-volume[i] 肯定没有更新过。

C++代码：

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int No7_BeiBao(int m, vector<int>&a, vector<pair<int, int>>&couple) {
        int n = a.size(), k = couple.size();    //couple中的编号是从1到n
        vector<int>val(k), volume(k);
        vector<bool>used(n, false);
        // k对可以看成 k个物品
        for (int i = 0; i < k; i++) {
            val[i] = 2;
            volume[i] = a[couple[i].first - 1] + a[couple[i].second - 1];
            used[couple[i].first - 1] = used[couple[i].second - 1] = true;
        }
        // 剩下单身的每只牛牛都是一个物品
        for (int i = 0; i < n; i++) {
            if (used[i])continue;
            val.push_back(1);
            volume.push_back(a[i]);
        }
        n = val.size();     // n个物品，背包容量是m
        vector<int>dp(m + 1, 0);
        for (int i = 0; i < n; i++) {
            for (int j = m; j >= volume[i]; j--) {
                dp[j] = max(dp[j], dp[j - volume[i]] + val[i]);
            }
        }
        return dp[m];
    }

int main(){
    int n,m,k;
    cin>>n>>m;
    vector<int>a(n);
    for(int i=0;i<n;i++)
        cin>>a[i];
    
    cin>>k;
    vector<pair<int, int>>couple(k);
    for(int i=0;i<k;i++)
        cin>>couple[i].first>>couple[i].second;
    
    cout<<No7_BeiBao(m, a, couple)<<'\n';
    return 0;
}