一、回顾dp背包
1. 0-1背包问题
问题描述：给定n个物品，每个物品有重量w[i]和价值v[i]，背包容量为W。每个物品只能选或不选，求最大价值。
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
C++实现：
int knapsack01(vector<int>& w, vector<int>& v, int W) {
int n = w.size();
vector<vector<int>> dp(n+1, vector<int>(W+1, 0));
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= W; ++j) {
if (j >= w[i-1]) {
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i-1]] + v[i-1]);
} else {
dp[i][j] = dp[i-1][j];
}
}
}
return dp[n][W];
}
// 空间优化版（一维数组）
int knapsack01_opt(vector<int>& w, vector<int>& v, int W) {
vector<int> dp(W+1, 0);
for (int i = 0; i < w.size(); ++i) {
for (int j = W; j >= w[i]; --j) { // 逆序更新
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
return dp[W];
}
2. 完全背包问题
问题描述：与0-1背包类似，但每个物品可以选无限次。
状态转移方程：
dp[i][j] = max(dp[i-1][j], dp[i][j-w[i]] + v[i])
C++实现：
int completeKnapsack(vector<int>& w, vector<int>& v, int W) {
int n = w.size();
vector<int> dp(W+1, 0);
for (int i = 0; i < n; ++i) {
for (int j = w[i]; j <= W; ++j) { // 正序更新
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
}
}
return dp[W];
}
3. 多重背包问题
问题描述：与0-1背包类似，但每个物品有数量限制s[i]。
解法：可以转化为0-1背包问题（二进制优化）
C++实现：
int multipleKnapsack(vector<int>& w, vector<int>& v, vector<int>& s, int W) {
vector<int> dp(W+1, 0);
for (int i = 0; i < w.size(); ++i) {
// 二进制优化拆分
int num = min(s[i], W / w[i]);
for (int k = 1; num > 0; k <<= 1) {
if (k > num) k = num;
num -= k;
for (int j = W; j >= w[i] * k; --j) {
dp[j] = max(dp[j], dp[j - w[i]*k] + v[i]*k);
}
}
}
return dp[W];
}
4. 分组背包问题
问题描述：物品被分为若干组，每组中只能选一个物品。
C++实现：
int groupKnapsack(vector<vector<int>>& groups_w, vector<vector<int>>& groups_v, int W) {
vector<int> dp(W+1, 0);
for (int k = 0; k < groups_w.size(); ++k) { // 遍历每组
for (int j = W; j >= 0; --j) { // 逆序
for (int i = 0; i < groups_w[k].size(); ++i) { // 遍历组内物品
if (j >= groups_w[k][i]) {
dp[j] = max(dp[j], dp[j - groups_w[k][i]] + groups_v[k][i]);
}
}
}
}
return dp[W];
}
5. 背包问题变种
5.1 恰好装满背包
初始化时dp[0] = 0，其他为-INF（求最大价值）或INF（求最小价值）
5.2 方案数问题
状态转移改为累加方案数
int countWays(vector<int>& w, int W) {
vector<int> dp(W+1, 0);
dp[0] = 1;
for (int i = 0; i < w.size(); ++i) {
for (int j = W; j >= w[i]; --j) {
dp[j] += dp[j - w[i]];
}
}
return dp[W];
}
5.3 二维费用背包
增加一维状态表示第二种限制
int twoDimensionalKnapsack(vector<int>& w1, vector<int>& w2, vector<int>& v, int W1, int W2) {
vector<vector<int>> dp(W1+1, vector<int>(W2+1, 0));
for (int k = 0; k < w1.size(); ++k) {
for (int i = W1; i >= w1[k]; --i) {
for (int j = W2; j >= w2[k]; --j) {
dp[i][j] = max(dp[i][j], dp[i-w1[k]][j-w2[k]] + v[k]);
}
}
}
return dp[W1][W2];
}
总结
0-1背包：物品只能选一次，内层循环逆序
完全背包：物品可选无限次，内层循环正序
多重背包：物品有数量限制，可二进制优化
分组背包：每组只能选一个物品，最内层循环组内物品
变种问题：注意初始化条件和状态转移含义的变化
掌握这些基本模型后，大多数背包问题都能通过适当变形解决。
二、题
1、P2196 [NOIP 1996 提高组] 挖地雷 - 洛谷
解题思路：建图，dp[i]表示为以i结尾的最大的地雷数，于是就有了
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define endl "\n"
const int MOD = 1e9 + 7;
using namespace std;
int main() {
int n; cin >> n;
vector<int>a(n + 1);
vector<int>dp(21, 0); // 表示以i点结束的最大结果
vector<vector<int>>graph(n + 1);
vector<vector<int>>way(n + 1);
for (int i = 1; i <= n; i++)
cin >> a[i];
int temp;
for (int i = 1; i < n; i++) {
for (int j = i + 1; j <= n; j++) {
cin >> temp;
if (temp) {
graph[i].push_back(j);
}
}
}
for (int i = 1; i <= n; i++)
dp[i] = a[i], way[i].push_back(i);
for (int i = 1; i <= n; i++) {
for (auto j : graph[i]) {
if (dp[j] < dp[i] + a[j]) {
dp[j] = dp[i] + a[j];
way[j] = way[i]; way[j].push_back(j);
}
}
}
int mx = 1;
for (int i = 1; i <= n; i++) {
mx = dp[mx] > dp[i] ? mx : i;
}
for (auto i : way[mx])
cout << i << " ";
cout << endl << dp[mx];
return 0;
}2、P4017 最大食物链计数 - 洛谷
解题思路：这个题目，我用找规律写的，如果一个物种，没用吃的，那就是生产者，如果一个物种没有被吃的物种，就是顶级物种，然后对生产者初始化为1，dp[i]+=dp[j],i是j的天敌既有了
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define endl "\n"
using namespace std;
const int MOD = 80112002;
int main() {
int n, m;
cin >> n >> m;
vector<vector<int>> graph(n + 1);
vector<int> in_degree(n + 1, 0);
vector<int> out_degree(n + 1, 0);
vector<int> dp(n + 1, 0);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
graph[a].push_back(b);
out_degree[a]++;
in_degree[b]++;
}
queue<int> q;
for (int i = 1; i <= n; i++) {
if (in_degree[i] == 0) {
dp[i] = 1;
q.push(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : graph[u]) {
dp[v] = (dp[v] + dp[u]) % MOD;
in_degree[v]--;
if (in_degree[v] == 0) {
q.push(v);
}
}
}
int ans = 0;
for (int i = 1; i <= n; i++) {
if (out_degree[i] == 0) {
ans = (ans + dp[i]) % MOD;
}
}
cout << ans << endl;
return 0;
}3、P1216 [IOI 1994] 数字三角形 Number Triangles - 洛谷
解题思路：毫无疑问dp[i][j]表示当前位置的最大值dp[i][j] = max( dp[i-1][j-1],dp[i-1][j] ) + nums[i][j]
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define endl "\n"
using namespace std;
int main() {
ios::sync_with_stdio(0);
cout.tie(0); cin.tie(0);
int r; cin >> r;
vector<vector<int>>nums(r + 1, vector<int>(r + 2, 0));
vector<vector<int>>dp(r + 1, vector<int>(r + 1, 0));
for (int i = 1; i <= r; i++)
for (int j = 1; j <= i; j++)
cin >> nums[i][j];
int ans = 0;
for (int i = 1; i <= r; i++) {
for (int j = 1; j <= i; j++) {
dp[i][j] = max(dp[i - 1][j - 1], dp[i - 1][j]) + nums[i][j];
if (i == r)ans = max(dp[i][j], ans);
}
}
cout << ans;
return 0;
}