46. 携带研究材料

二维

dp[i][j] 表示从下标为[0-i]的物品里任意取，放进容量为j的背包，价值总和最大是多少

i 来表示物品编号、j表示背包剩余容量

初始化第一行为（编号为0）的物品的价值，且背包空间需要大于等于它的重量，其余为0

遍历顺序是二维的，从上到下，从左到右

递推公式：判断此时能不能放下i号物品，

若不能，则维持和i - 1号相同dp

若能，分两种情况：

不放i，维持和i - 1号相同dp

放i， 背包剩余容量减小， dp在前一号基础上增加i的价值

两种情况取更大的数值

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
class Solution{
public:
    int function(int M, int N, vector<vector<int>>& items){
        vector<vector<int>>dp(M, vector<int>(N + 1, 0));
        for(int i = items[0][1]; i <= N; i++){
            dp[0][i] = items[0][0];
        }
        for(int i = 1; i < M; i++){
            for(int j = 0; j <= N; j++){
                if(items[i][1] > j){
                    dp[i][j] = dp[i - 1][j];
                }
                else{
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - items[i][1]] + items[i][0]);
                }
            }
        }
        return dp[M - 1][N];
    }
};
int main(){
    Solution solution;
    int M, N;
    cin >> M >> N;
    vector<vector<int>> items(M, vector<int>(2));
    for(int i = 0; i < M; i++){
        cin >> items[i][1];
    }
    for(int i = 0; i < M; i++){
        cin >> items[i][0];
    }
    int result = solution.function(M, N, items);
    cout << result << endl;
    return 0;
}

一维

把dp[i - 1]那一层拷贝到dp[i]上

表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]);

01 背包一维 DP逆序：保证每个物品只能被选一次（用的是选当前物品前的原始值）；

完全背包一维 DP正序：允许物品被重复选（用的是选当前物品后的新值）。

所以遍历顺序是逆序

    int function(int M, int N, vector<vector<int>>& items){
        vector<int>dp(N+1, 0);
        for(int i = items[0][1]; i <= N; i++){
            dp[i] = items[0][0];
        }
        for(int i = 1; i < M; i++){
            for(int j = N; j >= 0; j--){
                if(items[i][1] <= j){
                    dp[j] = max(dp[j], dp[j - items[i][1]] + items[i][0]);
                }
            }
        }
        return dp[N];
    }

416. 分割等和子集

回溯法，超时

剪枝：

总和是奇数，不行

回溯时同层去重，若值与之前相同，则证明之前的值也没有成功，故跳过

从大到小排序，若第一个数大于整体的一半，则肯定不行

bool backtracking(vector<int>& nums, int target, int index){
        if(sum > target){
            return false;
        }
        if(sum == target){
            return true;
        }
        if(index == nums.size()){
            return false;
        }
        for(int i = index; i < nums.size(); i++){
            if (i > index && nums[i] == nums[i-1]) {
                continue;
            }
            sum+=nums[i];
            if( backtracking(nums,target, i + 1)){
                return true;
            }
            sum-=nums[i];
        }
        return false;
    }
    bool canPartition(vector<int>& nums) {
        sort(nums.rbegin(), nums.rend());
        int target = 0;
        for(int num: nums){
            target += num;
        }
        if(target % 2 == 1){
            return false;
        }
        else{
            target = target / 2;
            if (nums[0] > target) {
                return false;
            }
            if(backtracking(nums, target, 0)){
                return true;
            }
        }
        return false;
    }

动态规划背包法

dp[j] 表示 → 从已遍历的元素中，能否选出一个子集，其和恰好等于 j；

dp[0] = true：和为 0 的子集一定存在

dp[j] = dp[j] || dp[j - num]; 但凡有真就选真

遍历顺序：01背包顺序，外部正序 内部逆序

    bool canPartition(vector<int>& nums) {
        int target = 0;
        for(int num: nums){
            target += num;
        }
        if(target % 2 == 1){
            return false;
        }
        target = target / 2;

        vector<bool> dp(target + 1, false);
        dp[0] = true;
        for(int num : nums){
            for(int j = target; j >= 0; j--){
                if(j < num){
                    continue;
                }
                dp[j] = dp[j] || dp[j - num];
                if(dp[target]){
                    return true;
                }
            }
        }
        return dp[target];
    }