【算法训练记录——Day43】

1.kamacoder52_携带研究材料

思路：这里每种材料可以选择无数次，因此属于完全背包，
首先回顾一下01背包的核心代码

for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = bagWeight; j >= weight[i]; j--) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    }
}

我们知道01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。
举例：dp[2] = dp[2-w[0]] + value[0];
w[0]不为0，则dp[2-w[0]] 肯定是前面的dp[i];
如果从后往前遍历，dp[2]之前的都已经初始化为0了
如果从前往后遍历，dp[2]之前的都是有值的，而dp[i]的定义是背包容量为i 的物品最大价值，每次for循环dp[i] + value[i] 相当于又多遍历了一次0~2；即重复添加了。

而完全背包的物品是可以添加多次的，所以要从小到大去遍历，即：

// 先遍历物品，再遍历背包
for(int i = 0; i < weight.size(); i++) { // 遍历物品
    for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
        dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);

    }
}

代码如下：

	#include<iostream>
	#include<vector>
	
	using namespace std;
	
	int main(){
	    int N, V;
	    cin >> N >> V;
	    vector<pair<int,int>> msg(N, {0, 0});
	    for(int i = 0; i < N; i++) {
	        int w, v;
	        cin >> w >> v;
	        msg[i] = {w, v};
	    }
	    
	    vector<int> dp(V+1, 0);
	    
	    for(int i = 0; i < N; i++) {
	        for(int j = msg[i].first; j <= V; j++) {
	            dp[j] = max(dp[j], dp[j-msg[i].first] + msg[i].second);
	        }
	    }
	    // for(auto i : dp)
	    //     cout << i << " ";
	    // cout << endl;
	    cout << dp[V];
	    return 0;
	}

2.leetcode518_零钱兑换Ⅱ

思路：dp[i]表示凑成总金额为 i 的组合数有 dp[i] 种
dp[i]如何计算？例如 如果已经有一个coins[i] = 1; 那么凑成5的有几种？因为5-1 = 4，因此只要凑成4的有几种，5就有几种。即 dp[j] = dp[j-coins[1]]; 如果 coins[i] = 2呢？dp[5] = dp[3] ,dp[j] = dp[j-coins[2]] …
因此：dp[j] = {dp[j-coins[i]]}，用dp[j]接收前一次结果，dp[j] += dp[j-coins[i]]；

	int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);

        dp[0] = 1;

        for(int i = 0; i < coins.size(); i++) {
            for(int j = coins[i]; j <= amount; j++) {
                dp[j] += dp[j-coins[i]];
            }
        }

        return dp[amount];
    }

3.leetcode377_组合总和Ⅳ

思路：回溯

class Solution {
    int res;
public:
    int backtracking(const vector<int>& nums, const int& target, int sum) {
        if(sum == target) {
            res++;
            return 0;
        } else if(sum > target) {
            return 1;
        }

        for(int i = 0; i < nums.size(); i++) {
            if(backtracking(nums, target, sum + nums[i]))
                break;
        }
        return 0;
    }

    int combinationSum4(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        backtracking(nums, target, 0);
        return res;
    }
};

回溯超时
因为本题不需要列出组合内容，尝试动态规划
和为target元素组合的个数
背包容量为target，每个元素可以遍历无数次，元素价值和体积都是nums[i],求最大组合数
dp[j] 表示 和为 j 的元素组合最大个数为 dp[j]
如果当前存在nums[i], dp[j] = dp[j-nums[i]],
dp[j] += dp[j-nums[i]];

	int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target+1, 0);
        dp[0] = 1;

        for(int j = 0; j <= target; j++) {
            for(int i = 0; i < nums.size(); i++) {
                if(j-nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]])
                    dp[j] += dp[j-nums[i]];
            }
        }

        return dp[target];
    }