01背包问题

动态规划中的核心在构建动态规划的矩阵和更新的方法。 1、矩阵行（i）:表示仅考虑[0, 1, ..., i]元素。 2、矩阵列（j）:表示最大容量为j。 此时dp[i][j]即表示相应的奖励，在选择i元素后，可选元素和最大容量都收缩。更新策略是外层累加i，内层增加最大容量j。可以采用滚动数组进行优化。

#include<iostream>
#include<vector>
#include<unordered_set>
using namespace std;
int main(){
    int n, m;
    cin >> n >> m;
    vector<int> nums(n, 0);
    for (int i = 0; i < n; ++i) {
        cin >> nums[i];
    }
    int k;
    cin >> k;
    vector<pair<int, int>> candy_1_2; // 表示需求的糖果数和对应牛牛的数量是1还是2
    unordered_set<int> mySet;
    for (int i = 0; i < k; ++i) {
        int connect1, connect2;
        cin >> connect1 >> connect2;  // 表示两个关联的编号
        candy_1_2.push_back({nums[connect1 - 1] + nums[connect2 - 1], 2});
        mySet.insert(connect1 - 1);
        mySet.insert(connect2 - 1);
    }
    for (int i = 0; i < n; ++i) {
        if (mySet.find(i) == mySet.end()) {
            candy_1_2.push_back({nums[i], 1});
        }
    }
    int n2 = candy_1_2.size(); // 表示可以单独选择或者不选择的项数
    vector<int> dp(m + 1, 0);
    for (int i = 0; i < n2; ++i) {  // 考虑【0， i】的闭区间内的所有元素
        vector<int> dp_before = dp;
        for (int j = 1; j <= m; ++j) {  // 此时背包的容量为j
            if (j < candy_1_2[i].first) {
                dp[j] = dp_before[j];  // 如果j较小,直接等于before
            } else {
                dp[j] = max(dp_before[j], dp_before[j - candy_1_2[i].first] + candy_1_2[i].second);
            }
        }
    }
    cout << dp[m] << endl;
    return 0;
}