day37|完全背包基础+leetcode 518.零钱兑换II ，377.组合总和II
完全背包理论基础
完全背包与01背包的不同在于01背包的不同物品每个都只可以使用一次，但是完全背包的不同物品可以使用无数次
在01背包理论基础中，为了使得物品只被使用一次，我们采取倒序遍历来控制
回顾：>>
for(int j = bagweight;j>=weight[i]; j--) { // 遍历背包容量
for(int i=0;i<weight.size();i++) { // 遍历物品
dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
}既然可以多次运用，那自然可以用正序遍历来控制
对于先遍历物品再遍历背包就是横向遍历
对于先遍历背包再遍历物品就是纵向遍历
动规五部曲
-
dp[i] [j]的含义：表示从下标为[0-i]的物品，每个物品可以取无限次，放进容量为j的背包，价值总和最大是多少。
-
确定递推公式：
// 正序遍历，如果能放下就一直装物品0
for (int j = weight[0]; j <= bagWeight; j++)
dp[0][j] = dp[0][j - weight[0]] + value[0];3.初始化：
// 初始化 dp
vector<vector<int>> dp(weight.size(), vector<int>(bagweight + 1, 0));
for (int j = weight[0]; j <= bagWeight; j++) {
dp[0][j] = dp[0][j - weight[0]] + value[0];
}4.确定遍历顺序：
先遍历背包再遍历物品 或者 先遍历物品再遍历背包都可以
for (int i = 1; i < n; i++) { // 遍历物品
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
}
} 或者
for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量
for (int i = 1; i < n; i++) { // 遍历物品
if (j < weight[i]) dp[i][j] = dp[i - 1][j];
else dp[i][j] = max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
}
}5.打印dp数组检查
1.携带材料
小明是一位科学家，他需要参加一场重要的国际科学大会，以展示自己的最新研究成果。他需要带一些研究材料，但是他的行李箱空间有限。这些研究材料包括实验设备、文献资料和实验样本等等，它们各自占据不同的重量，并且具有不同的价值。
小明的行李箱所能承担的总重量是有限的，问小明应该如何抉择，才能携带最大价值的研究材料，每种研究材料可以选择无数次，并且可以重复选择。
输入描述
第一行包含两个整数，n，v，分别表示研究材料的种类和行李所能承担的总重量
接下来包含 n 行，每行两个整数 wi 和 vi，代表第 i 种研究材料的重量和价值
输出描述
输出一个整数，表示最大价值。
这个例子与01背包的第一个示例题的最大区别就是这题可以重复选择
#include <iostream>
#include <vector>
using namespace std;
int main()
{
int n,bagweight;
cin>>n>>bagweight;
vector<int>weight(n);
vector<int>value(n);
for(int i=0;i<n;i++)
{
cin>>weight[i]>>value[i];
}
vector<vector<int>>dp(n,vector<int>(bagweight+1,0));
for(int j=weight[0];j<=bagweight;j++)//初始化
{
dp[0][j]=dp[0][j-weight[0]]+value[0];
}
for(int i=1;i<n;i++)//先遍历物品
{
for(int j=0;j<=bagweight;j++)//再遍历背包容量
{
if(j<weight[i])dp[i][j]=dp[i-1][j];//放不下去
else dp[i][j]=max(dp[i-1][j],dp[i][j-weight[i]]+value[i]);
}
}
cout<<dp[n-1][bagweight];
return 0;
}518. 零钱兑换 II
给你一个整数数组
coins表示不同面额的硬币，另给一个整数amount表示总金额。请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回
0。假设每一种面额的硬币有无限个。
题目数据保证结果符合 32 位带符号整数。
思路分析：题中“每一种面额的硬币有无限个”说明相同价值的物品可以重复放入背包，利用完全背包
注意本题中每一个组合并不强调组合内部元素的顺序，如1 1 2 和 2 1 1是同一个组合，所以我们要的是组合数
而不是排列数（强调元素顺序）
动规五部曲：
（1）dp数组含义：dp[j]代表装满容量为j的背包有几种方法
（2）确定递推公式：dp[j]+=dp[j-coins[j]];
（3）初始化：防止全部递推成0，dp[0]初始化为1
（4）确定遍历顺序：
本题由于是求组合数，所以应该先遍历物品后遍历背包：
1.先遍历物品后遍历背包 for(int i=0;i<coins.size();i++) { for(int j=coins[i];j<=amount;j++) { } } 假设coins[]=[1,2,5],amount=5 按照当前的遍历顺序，dp[]={1,2,2}和{2,2,1}会被当作一组 2.先遍历背包后遍历物品 for(int j=0;j<=amount;j++) { for(int i=0;i<coins.size();i++) } 按照当前的遍历顺序：dp[]={1,2,2}和{2,2,1}会被当作两组
具体可以看这几张图：
1.先遍历物品后遍历背包
2.先遍历背包后遍历物品
（5）打印dp数组
class Solution {
public:
int change(int amount, vector<int>& coins) {
int bagweight = amount;
vector<uint64_t>dp(bagweight+1,0);//uint64_t范围比int更大可以防止溢出
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[bagweight];
}
};377. 组合总和 Ⅳ
给你一个由 不同 整数组成的数组
nums，和一个目标整数target。请你从nums中找出并返回总和为target的元素组合的个数。题目数据保证答案符合 32 位整数范围。
示例 1：
输入：nums = [1,2,3], target = 4 输出：7 解释： 所有可能的组合为： (1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) 请注意，顺序不同的序列被视作不同的组合。
思路；这道题很明显和上一题不同，上一题零钱兑换是组合数，这道题就是排列数，由上一题可知先遍历背包后遍历物品
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int bagweight = target;
vector<uint64_t>dp(target+1,0);
dp[0]=1;//组成target为0的方法有dp[0]即1个
for(int j=0;j<=target;j++)
{
for(int i=0;i<nums.size();i++)
{
// dp[j]+=dp[j-nums[i]];直接这样会溢出，因为先遍历背包的时候j最初为0
if(j-nums[i]>=0 && dp[j]<INT_MAX-dp[j-nums[i]])//防止溢出
{
dp[j]+=dp[j-nums[i]];
}
}
}
return dp[target];
}
};