完全背包问题
题目链接：52. 携带研究材料（第七期模拟笔试）
文档讲解：代码随想录
状态：学习背包问题后AC
思路
完全背包问题：有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
1.二维dp数组：
关键在于递推公式的理解，与01背包类似，针对物品i可以选择或者不选择；若不放物品i：
如果放入物品i，首先要预留出容量，然后区别来啦：01背包的话选了i就要去i-1；而完全背包仍然可以在i层选取，因为有无数个！
针对初始化和遍历顺序看递推公式即可。
2.一维dp数组：
仍然可以将数组压缩成一维数组，一维数组具有覆盖性，要看遍历顺序：完全背包可重复放置，因此顺序遍历。
至于物品与背包的遍历顺序横竖不同：横：物品有序性，组合问题；竖：每次利用前面都是完值，排列问题。深刻理解！！！
本题使用完全背包思路即可解决。
题解
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 0, v = 0;
cin>>n>>v;
vector<int> weight(n,0);
vector<int> value(n,0);
// vector<vector<int>> dp(n,vector<int>(v+1,0));
for(int i = 0;i<n;i++)
{
cin>>weight[i];
cin>>value[i];
}
// for(int j = weight[0];j<=v;j++)
// {
// dp[0][j] = dp[0][j-weight[0]]+value[0];
// }
// for(int i = 1;i<n;i++)
// {
// for(int j = 0;j<=v;j++)
// {
// if(j>=weight[i])
// {
// dp[i][j] = max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
// }
// else dp[i][j] = dp[i-1][j];
// }
// }
// cout<<dp[n-1][v]<<endl;
vector<int> dp(v+1);
for(int i = 0;i<n;i++)
{
for(int j = weight[i];j<=v;j++)
{
dp[j] = max(dp[j],dp[j-weight[i]]+value[i]);
}
}
cout<<dp[v]<<endl;
return 0;
}
518.零钱兑换II
题目链接：518.零钱兑换II
文档讲解：代码随想录
状态：秒了
思路
越来越发现，背包问题可抽象为取值->满足目的（值、数量、次数等），经常解决类似回溯的排列组合问题。
本题是使用无限的硬币面值（体积）（完全背包），填满总金额（背包体积）的组合数，不是排列哦，记得遍历顺序。
题解
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<double> dp(amount+1);
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.组合总和Ⅳ
思路
本题说明在本文完全背包一维遍历顺序中，着重理解dp[3-1]与dp[3-2]:同样都是累加，注意遍历顺序对其影响。
先物品后容量->组合问题
先容量后物品->排列问题
题解
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<double> dp(target+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] += dp[j-nums[i]];
}
}
}
return dp[target];
}
};
70.爬楼梯（进阶）
题目链接：70.爬楼梯（进阶）
文档讲解：代码随想录
状态：轻松AC
思路
爬楼梯问题其实为完全背包问题，但是之前的爬楼梯情况少，可以用一个递归公式表达，而本题一次爬的楼梯数不确定，要用规范的背包解法。
楼顶阶数为背包总量，爬楼梯的种树为各个商品容量，所求为排列数。欧克了，可以写代码了。
题解
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n = 0, m = 0;
cin>>n>>m;
vector<int> dp(n+1,0);
dp[0] = 1;
for(int j = 0;j<=n;j++)
{
for(int i = 1;i<=m;i++)
{
if(j>=i)dp[j] += dp[j-i];
}
}
cout<<dp[n]<<endl;
return 0;
}