背包初步（0-1背包、完全背包）

当月光洒在我的脸上
我想我就快变了模样
有一种叫做撕心裂肺的汤
喝了它有神奇的力量

动态规划初步（完全背包）

0-1背包简介

在「背包 dp」前，先来看如下的例题：

P2871 [USACO07DEC] Charm Bracelet S - 洛谷

有n个物品和一个容量为m的背包，每个物品有重量 w和价值 v两种属性，要求选若干物品放入背包使背包中物品的总价值最大且背包中物品的总重量不超过背包的容量。

在上述例题中，由于每个物体只有两种可能的状态（取与不取），对应二进制中的0和1，这类问题便被称为「0-1 背包问题」。

dp状态f(i,j)为在只能放前i个物品的情况下，容量为j的背包所能达到的最大总价值。

考虑转移。假设当前已经处理好了前i-1个武平的所有状态，那么对于第i个物品:

当其不放入背包时，背包的剩余容量不变，背包中物品的总价值也不变，故这种情况的最大价值为f(i-1,j)；
当其放入背包时，背包的剩余容量会减小v，背包中物品的总价值会增大w，故这种情况的最大价值为f(i-1,j-w)+v。

由此可以得出状态转移方程： $f_{i,j}=\max(f_{i-1,j},f_{i-1,j-w_i}+v_i)$

但是，这里如果直接采用二维数组对状态进行记录，会出现MLE。可以考虑改用滚动数组的形式来优化。

由于对f(i)有影响的只有f(i-1)，可以去掉第一维，直接用f(i)来表示处理到当前物品时背包容量为i的最大价值，得出以下方程： $fj=max⁡(fj,fj−wi+vi)f_j=\max\left(f_j,f_{j-w_i}+v_i\right)$

大部分背包问题的转移方程都是在此基础上推导出来的。

核心代码就这个状态转移

for(int j=m;j>0;j--){if(w<=j)dp[j]=max(dp[j],dp[j-w]+d);
}

相关练习

P1048 [NOIP 2005 普及组] 采药 - 洛谷

P1049 [NOIP 2001 普及组] 装箱问题 - 洛谷

P1060 [NOIP 2006 普及组] 开心的金明 - 洛谷

278. 数字组合 - AcWing题库

P1164 小A点菜 - 洛谷

完全背包

完全背包模型与0-1背包类似，与0-1背包的区别仅在于一个物品可以选取无限次，而非仅能选取一次。

我们可以借鉴0-1背包的思路，进行状态定义：设f()i,j为只能选前i个物品时，容量为j的背包可以达到的最大价值。

虽然定义与 0-1 背包类似，但是其状态转移方程与0-1背包并不相同。

可以考虑一个朴素的做法：对于第i件物品，枚举其选了多少个来转移。这样做的时间复杂度是O(n³)的。

状态转移方程如下：

$fi,j=max⁡k=0+∞(fi−1,j−k×wi+vi×k)f_{i,j}=\max_{k=0}^{+\infty}(f_{i-1,j-k\times w_i}+v_i\times k)$

做一个简单的优化。可以发现，对于f(i,j)，只要通过f(i,j-w)转移就可以了。因此状态转移方程为：

$f_{i,j}=\max(f_{i-1,j},f_{i,j-w_i}+v_i)$

与 0-1 背包相同，我们可以将第一维去掉来优化空间复杂度

$f_{j}=\max(f_j,f_{j-w_i}+v_i)$

完全背包在写的时候根据题目目的的不同还要讨论两层for循环的前后顺序

如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。

完全背包和 0-1 背包的区别就在于对时间大小枚举的顺序不同，0-1背包在内层循环时是倒序的，因为每个物品只能选一次，倒序选择保证了第i个物品只会被放入背包一次；倒序循环满足了0-1背包问题中物品唯一的要求；而完全背包没有数量的限制所以可以正序枚举；

检查数组是否存在有效划分（前缀划分DP）

2369. 检查数组是否存在有效划分 - 力扣（LeetCode）

为了下面一道题能理解完全背包的划分思想，我已先看了这一道题；仔细观察发现居然是麻将！！

我们要在手牌中判断能否凑成对子，刻子和顺子；但是不能排序，所以必须要是子区间才可以；

一开始想的是用前两天学的滑动窗口，但是无法实现，就看题目的提示开始dp；直接套用分析的模板开始分析！

DP五部曲：

状态定义：

dp[i] 表示考虑数组的前 i 个元素（即 nums[0] 到 nums[i-1]）是否能被有效划分（true/false）。
状态转移：

通过三种子数组划分方式进行状态转移：
- 情况1：最后2个元素相等时，从 dp[i-2] 转移
  dp[i] |= (nums[i-1] == nums[i-2]) && dp[i-2]
- 情况2：最后3个元素相等时，从 dp[i-3] 转移
  dp[i] |= (i>=3 && nums[i-1]==nums[i-2] && nums[i-2]==nums[i-3]) && dp[i-3]
- 情况3：最后3个元素连续递增（差值1）时，从 dp[i-3] 转移
  dp[i] |= (i>=3 && nums[i-1]==nums[i-2]+1 && nums[i-2]==nums[i-3]+1) && dp[i-3]
状态转移方程
dp[i] = (最后2个相等且dp[i-2]) || (最后3个相等且dp[i-3]) || (最后3个连续递增且dp[i-3])
初始化（边界值）：
- dp[0] = true; // 空数组视为可划分
- dp[1] = false; // 单个元素不可划分
遍历顺序：
- 正序遍历索引 i 从 2 到 n（含端点）
- dp[i] 依赖 dp[i-2] 和 dp[i-3]，需优先计算小索引
返回形式：返回 dp[n]，表示整个数组能否被有效划分

分析完后，整体代码就呼之欲出

class Solution {
public:bool validPartition(vector<int>& a) {if(a.size()<2)return 0;vector<bool> dp(a.size()+1,0);dp[0]=1;for(int i=2;i<=a.size();i++){bool f1=0,f2=0,f3=0;if(a[i-1]==a[i-2]){f1=dp[i-2];}if(i>2&&a[i-1]==a[i-2]&&a[i-1]==a[i-3]){f2=dp[i-3];}if(i>2&&a[i-1]==a[i-2]+1&&a[i-1]==a[i-3]+2){f3=dp[i-3];}dp[i]=f1||f2||f3;}return dp[a.size()];}
};

从这题开始，下面的才是正宗的完全背包

单词拆分(求排列数)

139. 单词拆分 - 力扣（LeetCode）

铺垫那么久，终于开始引入正题；题目要求用给定的字符串数组中的元素拼出s，不限数量；不要求全部用上，但是拼的时候不能有重叠部分；我们需要判断能否拼出来；里面单词就是物品，字符串s就是背包，单词能否组成字符串s，就是问物品能不能把背包装满。也就是我们所学的完全背包；

DP五部曲：

状态定义:

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
状态转移:确定递推公式
- 如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true（j < i ）。
状态转移方程

if ([j, i] 这个区间的子串出现在字典里 && dp[j]是true) dp[i] = true
初始化(边界值):

从递推公式中可以看出，dp[i] 的状态依靠 dp[j]是否为true，那么dp[0]就是递推的根基，dp[0]一定为true，否则递推下去后面都都是false了。
遍历顺序:

题目中说是拆分为一个或多个在字典中出现的单词，所以这是完全背包。还要讨论两层for循环的前后顺序。这道题需要刚好拼满，不能重叠不能遗漏；所以是求排列数，外层for遍历背包，内层for循环遍历物品。（其实就是为了方便截取字符串去比较）
返回形式: dp[s.size()]就是最终结果。

class Solution {
public:bool wordBreak(string s, vector<string>& a) {vector<bool> dp(s.size()+1,0);dp[0]=1;for(int i=1;i<=s.size();i++){bool ff=0;for(int j=0;j<a.size();j++){if(a[j].size()<=i){string t=s.substr(i-a[j].size(),a[j].size());if(t==a[j])ff|=dp[i-t.size()];}}dp[i]=ff;}return dp[s.size()];}
};

疯狂的采药（求组合数）

P1616 疯狂的采药 - 洛谷

采草药，每种药没有限制，尽可能总价值越多越好；在这道题目中容易被草药的价值所迷惑；仔细分析总时间是背包，采摘草药所需的时间是物品，我们需要在时间里面分配采摘的情况使得草要的总价值最大；所以与上一题不同，这题需要物品在外，背包在内（求组合数）

DP五部曲：最大化价值

状态定义：

dp[j] 表示在时间限制 j 内能获得的最大价值：
- j 的取值范围：0 到 t（总可用时间）
- 目标：dp[t] 即时间限制 t 下的最大价值
状态转移:

采用完全背包策略（每种药材可采无限次）：dp[j] = max(dp[j], dp[j - 采药时间] + 药材价值)

转移说明：
- 不采当前药材：保留原值 dp[j]
- 采当前药材：从 j - 采药时间 转移，加上新价值
- 转移方程：
  dp[j] = max(dp[j], dp[j - a[i].fi] + a[i].se)
初始化:

dp[0] = 0; // 0 时间内无法采药，价值为 0
dp[j] = 0; // 所有初始值设为 0（通过全局数组初始化实现）
遍历顺序:

外层循环：遍历药材 i 从 1 到 m（物品维度）

内层循环：顺序枚举时间j从a[i].fi到t（容积维度）

从低到高正序遍历（完全背包特性）起点为当前药材所需时间 a[i].fi
返回形式:输出 dp[t] 即时间上限 t 时的最大价值

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=1e7+7;
int dp[N];
pii a[N];
void slove(){int t,m;cin>>t>>m;for(int i=1;i<=m;i++)cin>>a[i].fi>>a[i].se;for(int i=1;i<=m;i++){for(int j=a[i].fi;j<=t;j++)dp[j]=max(dp[j],dp[j-a[i].fi]+a[i].se);}cout<<dp[t];
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}

自然数拆分

279. 自然数拆分 - AcWing题库

趁热打铁，再来练一道；一样的思路一样的套路；这题的两种循环效果是一样的，不同顺序视为相同（属于相同的划分方案）

DP五部曲：整数划分问题（方案数统计）

状态定义

dp[j] 表示整数 j 可以被划分的方案数（模 2147483648），包括：
- 使用1到j的整数进行划分
- 允许重复使用相同的数
状态转移：

转移方程：dp[j] = (dp[j] + dp[j-i]) % M
- 含义：对于每个整数i，当前整数j的划分方案数等于：
  
  不使用 i 的方案数（dp[j]）加上使用至少一个 i 的方案数（dp[j-i]）
初始化（边界值）

dp[0] = 1; // 空划分：用0个数表示0的方案数为1
dp[i] = 0; // 其他值初始化为0（通过vector初始化）
遍历顺序
- 外层循环：枚举使用的数 i 从 1 到 4003（覆盖可能的n值）
- 内层循环：枚举整数 j 从 i 到 4003（从小到大遍历）
- 顺序要求：正序枚举背包容量（完全背包模型）
返回形式
- 输入目标整数 n
- 返回(dp[n] - 1) mod M其中：(减1表示排除只包含自身的情况)
  
  dp[n] 包含划分成单个整数的方案
- 当 dp[n] 为0时，输出 2147483647（即 M-1）

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define pii pair<int,int>
#define fi first
#define se second
const int N=4004;
const int M=2147483648;
int dp[N];
void slove(){int n;cin>>n;dp[0]=1;for(int i=1;i<=n;i++){for(int j=i;j<=n;j++){dp[j]=(dp[j]+dp[j-i])%M;}}int an=dp[n];if(an==0)an=M-1;elsean--;cout<<an<<endl;
} 
signed main(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int _=1;//cin>>_;while(_--)slove();return 0;
}