完全背包

完全背包和01背包的區別

純完全背包，遍歷背包和物品的順序是可以對調的，只要求得出最大價值，不要求湊成總和的元素的順序；
01背包，遍歷背包和物品的順序是不可以對調的（一維不行，二維是可以的）；
一維解法中 遍歷順序 主要就是用來保證物品 不被重復使用 的，而完全背包中物品本身就是可以重復使用的，所以就無所謂了。

完全背包

題目

思路與解法

#include <iostream>
#include <vector>
using namespace std;int main(){int n; // 物品種類int v; // 背包大小cin >> n >> v;vector<int> weight(n, 0); // 物品重量vector<int> value(n, 0); // 物品價值for(int i=0;i<n;i++){cin >> weight[i] >> value[i];}// for(int i=0;i<n;i++){//     cout<< weight[i];//     cout<< value[i]<<" ";// }// dp數組含義：//  dp[i]: 背包容量為i時，放入小于等于當前序號的物品所能達到的最大價值vector<int> dp(v+1, 0);// 先遍歷 物品for(int i=0;i<n;i++){// 后遍歷 背包for(int j=weight[i];j<=v;j++){dp[j] = max(dp[j-weight[i]]+value[i], dp[j]);}}cout << dp[v] << endl;return 0;
}

518. 零錢兌換 II

題目

思路與解法

class Solution {
public:int change(int amount, vector<int>& coins) {// dp數組含義：//  dp[i]: 總金額為i時，使用小于大于當前硬幣序號的硬幣能湊成總金額的方式總數vector<uint64_t> 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];}
};

377. 組合總和 Ⅳ

題目

思路與解法

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {//dp數組含義：組合的個數vector<uint64_t> dp(target+1, 0);dp[0] = 1;//先背包再物品 因為求的是排列for(int i=0;i<=target;i++){for(int j=0;j<nums.size();j++){if(nums[j] <= i) dp[i] += dp[i-nums[j]];}}return dp[target];}
};

57. 爬樓梯（第八期模擬筆試）

題目

思路與解法

 #include<iostream>#include <vector>using namespace std;int main(){int n, m; //n:總數，m：步長范圍cin >> n >> m;// dp數組含義：//  方式總數vector<int> dp(n+1, 0);dp[0] = 1;// 先背包再物品 因為求的是排列// 反過來就是求組合for(int i = 0;i<=n;i++){for(int j = 1;j<=m;j++){if(j <= i) dp[i] += dp[i-j]; }}cout << dp[n] << endl;return 0;}