h5制作网站,互联网公司招聘信息,手机广告设计软件,网站建设与管理计划目录 开端
01背包问题
AcWing 01背包问题
Luogu P2925干草出售
Luogu P1048采药
完全背包问题
AcWing 完全背包问题
Luogu P1853投资的最大效益
多重背包问题
AcWing 多重背包问题 I
AcWing 多重背包问题 II
Luogu P1776宝物筛选
混合背包问题
AcWing 混合背包问题…目录 开端
01背包问题
AcWing 01背包问题
Luogu P2925干草出售
Luogu P1048采药
完全背包问题
AcWing 完全背包问题
Luogu P1853投资的最大效益
多重背包问题
AcWing 多重背包问题 I
AcWing 多重背包问题 II
Luogu P1776宝物筛选
混合背包问题
AcWing 混合背包问题
Luogu P1833樱花
二维费用背包问题
AcWing 二维费用的背包问题
Luogu P1507NASA的食物计划
分组背包问题
AcWing 分组背包问题
Luogu P1757 通天之分组背包 开端
关于背包问题嗯一直学不明白暑假咸的没事又拾起来学了一下跟着这位大佬整理的思路背包九讲——全篇详细理解与代码实现-CSDN博客对背包的思想有了一定清晰的理解大佬的文章有些长所以跟着自己的思路再整理一下。
为了方便统一先定义一下 c[i]表示代价 w[i]表示价值 dp[i][j]表示前i个物品花费代价为j的可以获得的最大代价 p[i]表示第i种物品最多有p[i]件 01背包问题 定义 dp[i][j]表示前i个物品恰放入一个容量为j的背包下可以获得的最大代价 子问题第i1件物品状态 ①不选dp[i][j]dp[i-1][j]②选dp[i][j]dp[i][j-c[i]]w[i] 状态转移方程 dp[i][j]max(dp[i-1][j],dp[i][j-c[i]]w[i]) 优化空间复杂度 O(V*N) for(int i1;in;i)for(int jc[i];jV;j--)dp[i][j]max(dp[i-1][j],dp[i-1][j-c[i]]w[i]); O(V) for(int i1;in;i)for(int jV;jc[i];j)dp[j]max(dp[j],dp[j-c[i]]w[i]); 关于顺序和逆序 逆序表示dp[j]max(dp[j],dp[j-c[i]]w[i])由dp[i][j]max(dp[i-1][j],dp[i-1][j-c[i]]w[i])转移过来的
顺序表示dp[j]max(dp[j],dp[j-c[i]]w[i])由dp[i][j]max(dp[i][j],dp[i][j-c[i]]w[i])转移过来的 初始化问题 ①要求恰好装满dp[i]-∞,dp[0]0;②只要求价值最大dp[i]0; AcWing 01背包问题 const int N 1010;
int c[N], w[N], dp[N];
inline void solve()
{int N, V;cin N V;for (int i 1; i N; i)cin c[i] w[i];for (int i 1; i N; i)for (int j V; j c[i]; j--)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout dp[V] endl;
}
Luogu P2925干草出售
const int N 5e4 10;
int w[N], dp[N];
inline void solve()
{int C, H;cin C H;for (int i 1; i H; i)cin w[i];for (int i 1; i H; i)for (int j C; j w[i]; j--)dp[j] max(dp[j], dp[j - w[i]] w[i]);cout dp[C] endl;
}
Luogu P1048采药
const int N 1010;
int c[N], w[N], dp[N];
inline void solve()
{int T, M;cin T M;for (int i 1; i M; i)cin c[i] w[i];for (int i 1; i M; i)for (int j T; j c[i]; j--)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout dp[T] endl;
}
完全背包问题 定义 dp[i][j]表示前i种物品恰放入一个容量为j的背包下可以获得的最大代价 子问题第i种物品状态 ①不选该种物品dp[i][j]dp[i-1][j];
②选不同件该种物品选0件、1件、2件……k件dp[i][j]dp[i-1][j-c[i]*k]w[i]*k; 状态转移方程 dp[i][j]max(dp[i-1][j-c[i]*k]w[i]*k) 0c[i]*kj 优化空间复杂度 O(N*∑(V/c[i])) for(int i1;in;i)for(int jc[i];jV;j)for(int k0;c[i]*kj;k)dp[i][j]max(dp[i][j],dp[i-1][j-c[i]*k]w[i]*k);
# 第一个参数因为k0时就相当于dp[i-1][j]; O(V*N)转化为01背包问题 for(int i1;in;i)for(int jc[i];jj;j)dp[j]max(dp[j],dp[j-c[i]]w[i]);
//等价于dp[i][j]max(dp[i-1][j],dp[i][j-c[i]]w[i]);(不取该物品取不同件) 关于顺序和逆序 逆序表示dp[j]max(dp[j],dp[j-c[i]]w[i])由dp[i][j]max(dp[i-1][j],dp[i-1][j-c[i]]w[i])转移过来的
顺序表示dp[j]max(dp[j],dp[j-c[i]]w[i])由dp[i][j]max(dp[i-1][j],dp[i][j-c[i]]w[i])转移过来的 初始化问题 ①要求恰好装满dp[i]-∞,dp[0]0;②只要求价值最大dp[i]0; AcWing 完全背包问题 const int N 1010;
int c[N], w[N], dp[N];
inline void solve()
{int N, V;cin N V;for (int i 1; i N; i)cin c[i] w[i];for (int i 1; i N; i)for (int j c[i]; j V; j)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout dp[V] endl;
}
Luogu P1853投资的最大效益
const int N 1e6 10;
int c[N], w[N], dp[N];
inline void solve()
{int s, n, d;cin s n d;for (int i 1; i d; i)cin c[i] w[i];while (n--){for (int i 1; i d; i)for (int j c[i]; j s; j)dp[j] max(dp[j], dp[j - c[i]] w[i]);s dp[s];}cout s endl;
}
int main( 这个题目有个小坑 所以要做一下处理除以1000防止爆空间
const int N 1e6 10;
int c[N], w[N], dp[N];
inline void solve()
{int s, n, d;cin s n d;for (int i 1; i d; i)cin c[i] w[i];while (n--){for (int i 1; i d; i)for (int j c[i] / 1000; j s / 1000; j)dp[j] max(dp[j], dp[j - c[i] / 1000] w[i]);s dp[s / 1000];}cout s endl;
}
多重背包问题 定义 dp[i][j]表示前i种物品恰放入一个容量为j的背包下可以获得的最大代价 子问题第i种物品状态 ①不选该种物品dp[i][j]dp[i-1][j];
②选不同件该种物品选1件、2件……p[i]件dp[i][j]dp[i-1][j-c[i]*k]w[i]*k; 状态转移方程 dp[i][j]max(dp[i-1][j-c[i]*k]w[i]*k) 0kp[i] 转化为01背包问题 方法一O(V*∑p[i]) for(int i1;in;i)for(int jV;jc[i];j--)for(int k1;c[i]*kjkp[i];k)dp[j]max(dp[j],dp[j-c[i]*k]w[i]*k);
# 第一个参数因为k0时就相当于dp[i-1][j]; 方法二二进制优化O(N*log(p)*V) for (int i 1; i N; i){int a, b, s;cin a b s;int k 1;while (k s) //0……2^k-1部分的系数1248……{cnt;c[cnt] k * a;w[cnt] k * b;s - k;k * 2;}if (s 0) //2^k……s部分的系数 s-2^k{cnt;c[cnt] s * a;w[cnt] s * b;}}N cnt; //更新总数量for (int i 1; i N; i) //01背包问题for (int j V; j c[i]; j--)dp[j] max(dp[j], dp[j - c[i]] w[i]); for (int i 1; i n; i){cin c[i] w[i] p[i];int s min(p[i], W / w[i]);for (int k 1; s 0; k 1){k min(k, s);s - k;for (int j W; j k * w[i]; j--){dp[j] max(dp[j], dp[j - k * w[i]] k * c[i]);}}} 初始化问题 ①要求恰好装满dp[i]-∞,dp[0]0;②只要求价值最大dp[i]0; 方法一
AcWing 多重背包问题 I const int N 110;
int c[N], w[N], p[N], dp[N];
inline void solve()
{int N, V;cin N V;int cnt 0;for (int i 1; i N; i)cin c[i] w[i] p[i];for (int i 1; i N; i)for (int j V; j c[i]; j--)for (int k 1; c[i] * k j k p[i]; k)dp[j] max(dp[j], dp[j - c[i] * k] w[i] * k);cout dp[V] endl;
}
方法二
AcWing 多重背包问题 II const int N 20010; //注意初始化否则会越界
int c[N], w[N], dp[N];
inline void solve()
{int N, V;cin N V;int cnt 0;for (int i 1; i N; i){int a, b, s;cin a b s;int k 1;while (k s) //0……2^k-1部分的系数1248……{cnt;c[cnt] k * a;w[cnt] k * b;s - k;k * 2;}if (s 0) //2^k……s部分的系数 s-2^k{cnt;c[cnt] s * a;w[cnt] s * b;}}N cnt; //更新总数量for (int i 1; i N; i) //01背包问题for (int j V; j c[i]; j--)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout dp[V] endl;
}
Luogu P1776宝物筛选
const int N 1e6 10; // 注意初始化否则会越界
int c[N], w[N], dp[N];
inline void solve()
{int n, W;cin n W;int cnt 0;for (int i 1; i n; i){int a, b, s;cin a b s;int k 1;while (k s){cnt;w[cnt] k * a;c[cnt] k * b;s - k;k * 2;}if (s 0){cnt;w[cnt] s * a;c[cnt] s * b;}}n cnt;for (int i 1; i n; i)for (int j W; j c[i]; j--)dp[j] max(dp[j], dp[j - c[i]] w[i]);cout dp[W] endl;
}
简化
const int N 1e6 10; // 注意初始化否则会越界
int c[N], w[N], p[N], dp[N];
inline void solve()
{int n, W;cin n W;for (int i 1; i n; i){cin c[i] w[i] p[i];int s min(p[i], W / w[i]);for (int k 1; s 0; k 1){k min(k, s);s - k;for (int j W; j k * w[i]; j--){dp[j] max(dp[j], dp[j - k * w[i]] k * c[i]);}}}cout dp[W] endl;
}
混合背包问题 01背包、完全背包、多重背包的混合状态转移 for (int i 1; i N; i){cin c[i] w[i] p[i];// 01背包if (p[i] -1)for (int j V; j c[i]; j--)dp[j] max(dp[j], dp[j - c[i]] w[i]);// 完全背包else if (p[i] 0)for (int j c[i]; j V; j)dp[j] max(dp[j], dp[j - c[i]] w[i]);// 多重背包二进制优化else{int s min(p[i], V / c[i]);for (int k 1; s 0; k 1){k max(k, s);s - k;for (int j V; j k * c[i]; j--)dp[j] max(dp[j], dp[j - k * c[i]] k * w[i]);}}} AcWing 混合背包问题 const int N 1e6 10; // 注意初始化否则会越界
int c[N], w[N], p[N], dp[N];
inline void solve()
{int N, V;cin N V;for (int i 1; i N; i){cin c[i] w[i] p[i];// 01背包if (p[i] -1)for (int j V; j c[i]; j--)dp[j] max(dp[j], dp[j - c[i]] w[i]);// 完全背包else if (p[i] 0)for (int j c[i]; j V; j)dp[j] max(dp[j], dp[j - c[i]] w[i]);//或将完全背包转化为多重01背包sV/c[i]// 多重背包二进制优化else{int s min(p[i], V / c[i]);for (int k 1; s 0; k 1){k min(k, s);s - k;for (int j V; j k * c[i]; j--)dp[j] max(dp[j], dp[j - k * c[i]] k * w[i]);}}}cout dp[V] endl;
}
Luogu P1833樱花
const int N 1e6 10; // 注意初始化否则会越界
int c[N], w[N], p[N], dp[N];
inline void solve()
{int m1, m2, s1, s2, N;scanf(%d:%d %d:%d %d, m1, s1, m2, s2, N);int V m2 * 60 s2 - m1 * 60 - s1;for (int i 1; i N; i){cin c[i] w[i] p[i];int s;if (p[i] 0) // 完全转化为多重s V / c[i];elses min(p[i], V / c[i]);for (int k 1; s 0; k 1){k min(k, s);s - k;for (int j V; j k * c[i]; j--)dp[j] max(dp[j], dp[j - k * c[i]] k * w[i]);}}cout dp[V] endl;
}
二维费用背包问题 定义每件物品需要同时花费两种不同的代价 dp[i][j][k]表示前i种物品付出两种代价分别最大为j和k时可获得的最大价值 状态转移方程 dp[i][j][k]max(dp[i-1][j][k],dp[i-1][j-c[i]][k-m[i]]w[i]) 01背包代码完全背包、多重背包可以类比 for(int i1;in;i)for(int jV;jc[i];j--)for(int kM;km[i];k--)dp[j][k]max(dp[j][k],dp[j-c[i]][k-m[i]]w[i]); AcWing 二维费用的背包问题 const int N 1010; // 注意初始化否则会越界
int c[N], w[N], m[N], dp[N][N];
inline void solve()
{int N, V, M;cin N V M;for (int i 1; i N; i){cin c[i] m[i] w[i];for (int j V; j c[i]; j--)for (int k M; k m[i]; k--)dp[j][k] max(dp[j][k], dp[j - c[i]][k - m[i]] w[i]);}cout dp[V][M] endl;
}
Luogu P1507NASA的食物计划
const int N 1010; // 注意初始化否则会越界
int c[N], w[N], m[N], dp[N][N];
inline void solve()
{int V, M, N;cin V M N;for (int i 1; i N; i){cin c[i] m[i] w[i];for (int j V; j c[i]; j--)for (int k M; k m[i]; k--)dp[j][k] max(dp[j][k], dp[j - c[i]][k - m[i]] w[i]);}cout dp[V][M] endl;
}
分组背包问题 定义 dp[k][j]表示前k组物品花费代价j能取得的最大价值 子问题第k组物品状态 ①不选该组物品dp[k][j]dp[k-1][j];
②选该组物品dp[k][j]dp[k-1][j-c[i]w[i]] 物品i属于k组 状态转移方程 dp[k][j]max(dp[k-1][j],dp[k-1][j-c[i]]w[i]) 模板 for (int k 1; k N; k){int s;cin s; // 第k组的物品数量for (int i 1; i s; i)cin c[i] w[i]; // 组中每个物品i的属性for (int j V; j 0; j--)for (int i 1; i s; i) // 保证每组物品只能选一个可以覆盖之前组内物品最优解的来取最大值if (j c[i])dp[j] max(dp[j], dp[j - c[i]] w[i]);} AcWing 分组背包问题 const int N 110; // 注意初始化否则会越界
int c[N], w[N], m[N], dp[N];
inline void solve()
{int N, V;cin N V;for (int k 1; k N; k){int s;cin s; // 第k组的物品数量for (int i 1; i s; i)cin c[i] w[i]; // 组中每个物品i的属性for (int j V; j 0; j--)for (int i 1; i s; i) // 保证每组物品只能选一个可以覆盖之前组内物品最优解的来取最大值if (j c[i])dp[j] max(dp[j], dp[j - c[i]] w[i]);}cout dp[V] endl;
}
Luogu P1757 通天之分组背包
const int N 110; // 注意初始化否则会越界
const int M 1010; // 注意初始化否则会越界
int c[M], w[M], dp[M];
int g[N][N], b[M]; // g[k][i]表示小组k种第i个物品的编号,b[k]表示小组k的物品1
inline void solve()
{int N, V;cin V N;int t 0, k 0;for (int i 1; i N; i){cin c[i] w[i] k;t max(t, k); // 求小组的组数b[k]; // 小组k的物品1g[k][b[k]] i; // 小组k中第b[k]个物品的编号为i;}for (int k 1; k t; k)for (int j V; j 0; j--)for (int i 1; i b[k]; i)if (j c[g[k][i]])dp[j] max(dp[j], dp[j - c[g[k][i]]] w[g[k][i]]);cout dp[V] endl;
}
