494. 目标和

// 1、dp[j] 重量为j的背包的最大价值
// 2、递推公式：dp[j]=max(dp[j], dp[j-1]+coins[i]])
// 3、初始化：dp[0]=0;

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int result=0;
        vector<int> dp(amount+1, 0);
        for (int i=0; i<coins.size(); i++){
            cout << "epoch" <<i << " ";
            for (int j=i+1; j<amount+1; j++){
                dp[j] = max(dp[j], dp[j-1]+coins[i]);
                if (dp[j]==amount) result++;
                cout<<dp[j]<<" ";
            }
            cout << endl;
        }

        for (int j=0; j<amount+1; j++) cout<<dp[j]<<" ";
        cout << endl;
        return result;
    }
};

完全背包

# include<iostream>
# include<vector>

using namespace std;

int main(){
    int type=0, space=0;
    
    cin >> type >>space;
    
    vector<int> dp(space+1, 0);
    vector<int> weight(type, 0);
    vector<int> value(type, 0);
    
    for(int i = 0; i < type; i++) {
        cin>>weight[i];
        cin>>value[i];
    }
    for (int i=0; i<type; i++){
        for (int j=weight[i]; j<=space; j++){
            dp[j] = max(dp[j], dp[j-weight[i]]+value[i]);
        }
    }
    
    // cout<<endl;
    // for (int i=0; i<=space; i++){
    //     cout << dp[i] <<" ";
    // }
    // cout <<endl;
    
    cout << dp[space] <<endl;
    
}

主要就是在遍历背包时从前往后遍历，由于可以一个种类的物品可以无限使用，所以背包容量增加时，从前往后遍历也能使用到左侧更新完价值但容量更小的背包的数据。

518. 零钱兑换 II

看不懂

// 1、dp[j] 总金额为j的背包被不同大小和个数的硬币装满的情况
// 2、递推公式：dp[j]=max(dp[j], dp[j-1]+coins[i]])
// 3、初始化：dp[0]=0;

// 硬币重量为1，价值为coins[i]

class Solution {
public:
    int change(int target, vector<int>& nums) {
        int result=0;
        vector<int> dp(target+1, 0);
        vector<int> weight(nums.size(), 1);
        dp[0]=1;
        for (int j=0; j<=target; j++){ //按照背包价值为索引遍历不同价值的背包
            for (int i=0; i<nums.size(); i++){ //尝试向不同大小的背包里放不同价格的硬币
                if (j>=nums[i] && dp[j]<INT_MAX - dp[j - nums[i]])
                    dp[j] += dp[j-nums[i]];
            }
            cout<<"背包价值为" << j << "的背包被满足有多少种情况:" ;
            for (int j=0; j<dp.size(); j++) cout << dp[j] << " ";
            cout <<endl;
        }

        return dp[target];
    }
};

组合总和 Ⅳ

为什么这题我能写出来，上题写不出来？

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        int result=0;
        vector<int> dp(target+1, 0);
        vector<int> weight(nums.size(), 1);
        dp[0]=1;
        for (int j=0; j<=target; j++){ //按照背包价值为索引遍历不同价值的背包
            for (int i=0; i<nums.size(); i++){ //尝试向不同大小的背包里放不同价格的硬币
                if (j>=nums[i] && dp[j]<INT_MAX - dp[j - nums[i]])
                    dp[j] += dp[j-nums[i]];
            }
            // cout<<"背包价值为" << j << "的背包被满足有多少种情况:" ;
            // for (int j=0; j<dp.size(); j++) cout << dp[j] << " ";
            // cout <<endl;
        }

        return dp[target];
    }
};