佛山专业的网站建设,crm客户管理系统官网,怎么查域名的注册人,门户网站开发用什么框架好动态规划(Dynamic Programming)
背包问题 目录动态规划(Dynamic Programming)背包问题01背包问题输入格式输出格式数据范围输入样例输出样例#xff1a;二维一维完全背包问题多重背包问题输入格式输出格式数据范围输入样例输出样例#xff1a;数据范围二进制优化分组背包问题…动态规划(Dynamic Programming)
背包问题 目录动态规划(Dynamic Programming)背包问题01背包问题输入格式输出格式数据范围输入样例输出样例二维一维完全背包问题多重背包问题输入格式输出格式数据范围输入样例输出样例数据范围二进制优化分组背包问题输入格式输出格式数据范围输入样例输出样例01背包问题
动态规划
状态表示 f[i][j] 集合所有考虑前i个物品且体积不大于j的全部选法属性Max 状态计算集合的划分 有 N件物品和一个容量是 V的背包。每件物品只能使用一次。 第 i 件物品的体积是 viv_ivi价值是wiw_iwi。 求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品数量和背包容积。 接下来有 N 行每行两个整数 vi,wiv_i,w_ivi,wi用空格隔开分别表示第 i 件物品的体积和价值。 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤10000NV≤1000 0vi,wi≤10000 vi,wiv_i,w_ivi,wi≤1000 输入样例 4 5
1 2
2 4
3 4
4 5输出样例 8二维 状态f[i][j]定义前 i个物品背包容量 j下的最优解最大价值 当背包容量够需要决策选与不选第 i 个物品 不选f[i][j] f[i-1][j]选f[i][j]f[i-1][j-v[i]]w[i]我们的决策是如何取到最大价值因此以上两种情况取max() 代码 #include iostream
#include algorithm
using namespace std;
const int N 1010;
int v[N], w[N];
int f[N][N];
int main() {int n, m;cin n m;for (int i 1; i n; i)cin v[i] w[i];for (int i 1; i n; i) {for (int j 1; j m; j) {f[i][j] f[i - 1][j];if (v[i] j) f[i][j] max(f[i][j], f[i -1][j - v[i]] w[i]);}}cout f[n][m];return 0;
}一维
我们定义的状态f[i][j]可以求得任意合法的i与j最优解但题目只需要求得最终状态f[n][m]因此我们只需要一维的空间来更新状态。
#include iostream
#include algorithm
using namespace std;
const int N 1010;
int v[N], w[N];
int f[N];
int main() {int n, m;cin n m;for (int i 1; i n; i)cin v[i] w[i];for (int i 1; i n; i) {for (int j m; j v[i]; --j) {f[j] max(f[j], f[j - v[i]] w[i]);}}cout f[m];return 0;
}完全背包问题
动态规划
状态表示 f[i][j] 集合所有考虑前i个物品且体积不大于j的全部选法属性Max 状态计算集合的划分
f[i][j]第i个物品选了k个,先去掉k个物品i再加回来k个物品i
f[i][j] f[i-1][j-v[i]*k]w[i]*k
暴力dp
#include iostreamusing namespace std;
const int N 1010;
int f[N][N],v[N], w[N];
int main() {int n, m;cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j 1; j m; j) {for (int k 0; k * v[i] j; k) {f[i][j] max(f[i][j],f[i - 1][j - k * v[i]] k * w[i]);// cout f[i][j];}}}cout f[n][m];return 0;
}我们可以发现 f[i,j]Max(f[i-1,j],f[i-1,j-v]w,f[i-1.j-2v]2w,...,f[i-1.j-kv]kw f[i,j-v]Max( f[i-1,j-v],f[i-1.j-2v]w,...,f[i-1.j-kv](k-1)w 代码
#include iostream
// #include algorithm
using namespace std;
const int N 1010;
int f[N][N],v[N], w[N];
int main() {int n, m;cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j 1; j m; j) {f[i][j] f[i-1][j];if (j v[i]) f[i][j] max(f[i][j], f[i][j-v[i]] w[i]); }}cout f[n][m];return 0;
}一维代码
#include iostream
// #include algorithm
using namespace std;
const int N 1010;
int f[N],v[N], w[N];
int main() {int n, m;cin n m;for (int i 1; i n; i) cin v[i] w[i];for (int i 1; i n; i) {for (int j v[i]; j m; j) {// f[i][j] f[i-1][j];f[j] max(f[j], f[j-v[i]] w[i]); }}cout f[m];return 0;
}多重背包问题
动态规划
状态表示 f[i][j] 集合所有考虑前i个物品且体积不大于j的全部选法属性Max 状态计算集合的划分 题目描述 有 N 种物品和一个容量是 V 的背包。 第 i种物品最多有 sis_isi 件每件体积是 viv_ivi 价值是 wiw_iwi 。 求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。 输入格式 第一行两个整数NV用空格隔开分别表示物品种数和背包容积。 接下来有 N 行每行三个整数 viv_ivi, wiw_iwi, sis_isi 用空格隔开分别表示第 i种物品的体积、价值和数量。 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤100 0viv_ivi, wiw_iwi, sis_isi ≤100 输入样例 4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例 10代码
#include iostream
using namespace std;
const int N 110;
int f[N][N], w[N], v[N], s[N];
int main() {int n, m;cin n m;for (int i 1; i n; i) cin v[i] w[i] s[i];for (int i 1; i n; i)for (int j 1; j m; j) {for (int k 0; k * v[i] j k s[i]; k) {f[i][j] max(f[i][j], f[i - 1][j - k * v[i]] k * w[i]);}}cout f[n][m];return 0;
}当数据范围扩大 数据范围 0N≤1000 0V≤2000 0viv_ivi, wiw_iwi, sis_isi ≤2000 f(i, j) Max(f(i-1,j),f(i-1,j-v)w,f(i-1,j-2v)2w...f(i-1,j-sv)sw)
f(i, j-v) Max(f(i-1,j-v),f(i-1,j-2v)w,f(i-1,j-3v)2w...f(i-1,j-sv)(s-1)w,f(i, j) Max(f(i-1,j),f(i-1,j-v)w,f(i-1,j-2v)2w...f(i-1,j-(s1)v)sw)所以不能用完全背包问题解决
我们可以采用二进制优化01背包问题的方法
二进制优化
给出一堆苹果和10个箱子选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,…512分到10个箱子里那么由于任何一个数字x∈[0,1023] (第11个箱子才能取到1024评论区有讨论这个)都可以从这10个箱子里的苹果数量表示出来但是这样选择的次数就是 ≤10次
代码
#include iostream
using namespace std;
const int N 1e5 10;
int v[N], w[N];
int f[2020];
int main() {int n, m;cin n m;int cnt 0;while (n--) {int a, b, s;cin a b s;int k 1;while (k s) {v[cnt] a * k;w[cnt] b * k;s - k;k * 2;}if (s){v[cnt] a * s;w[cnt] b * s;}}n cnt;for (int i 1; i n; i) {for (int j m; j v[i]; --j) {f[j] max(f[j], f[j - v[i]] w[i]);}}cout f[m];return 0;
}分组背包问题 有 N 组物品和一个容量是 V的背包。 每组物品有若干个同一组内的物品最多只能选一个。 每件物品的体积是vi,jv_{i,j}vi,j价值是wi,jw_{i,j}wi,j其中 i 是组号j 是组内编号。 求解将哪些物品装入背包可使物品总体积不超过背包容量且总价值最大。 输出最大价值。 输入格式 第一行有两个整数 NV用空格隔开分别表示物品组数和背包容量。 接下来有 N 组数据 每组数据第一行有一个整数 SiS_{i}Si表示第 i 个物品组的物品数量每组数据接下来有 SiS_{i}Si 行每行有两个整数vi,jv_{i,j}vi,j,wi,jw_{i,j}wi,j用空格隔开分别表示第 i个物品组的第 j 个物品的体积和价值 输出格式 输出一个整数表示最大价值。 数据范围 0N,V≤100 0Si≤100 0vi,jv_{i,j}vi,j,wi,jw_{i,j}wi,jj≤100 输入样例 3 5
2
1 2
2 4
1
3 4
1
4 5输出样例 8 代码
#include iostream
using namespace std;
const int N 110;
int v[N], w[N];
int f[110];
int main() {int n, m;cin n m;for (int i 1; i n; i) {int s;cin s;for (int j 1; j s; j) {cin v[j] w[j];}for (int k m; k 1; --k) {for (int j 1; j s; j) {if (v[j] k)f[k] max(f[k], f[k - v[j]] w[j]);}} }cout f[m];return 0;
}
