哈尔滨 网站建设公司,网站建设如何选择良好的服务器,网站开发流程进度表,蓬莱有做网站的吗题目一 01背包
有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi#xff0c;价值是 wi。
求解将哪些物品装入背包#xff0c;可使这些物品的总体积不超过背包容量#xff0c;且总价值最大。 输出最大价值。
输入格式
第一行两个整数… 题目一 01背包
有 N 件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi价值是 wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品数量和背包容积。
接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤1000 0vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5输出样例
8
分析 如果当前j大于v的情况下可以得出状态转移方程为f[i,j]max(f[i-1,j],f[i-1,j-v]w)
否则f[i,j]f[i-1,j]
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N1010;int v[N],w[N];
int f[N][N];
int n,m;int main()
{cinnm;for(int i1;in;i)cinv[i]w[i];for(int i1;in;i){for(int j0;jm;j){f[i][j]f[i-1][j];if(jv[i]) f[i][j]max(f[i][j],f[i-1][j-v[i]]w[i]);}}coutf[n][m]endl;return 0;
}
优化成一维
观察代码可以发现只用到了前一维的状态所以我们可以去掉第一维
此时状态为前n件物品中总价值不超过j的状态
我们去掉一维之后注意j要逆序枚举由于我们的状态转移方程是f[j]max(f[j],f[j-v[i]]w[i]);
如果不逆序枚举的话f[j-v[i]]本来应该是第i-1轮的状态但是会成为第i轮的状态即污染。
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N1010;int f[N];
int w[N];
int v[N];int main()
{int n,m;cinnm;for(int i1;in;i) cinv[i]w[i];for(int i1;in;i)for(int jm;jv[i];j--){f[j]max(f[j],f[j-v[i]]w[i]);//coutf[j]:f[j]endl;}coutf[m]endl;
}
题目二 完全背包
有 N种物品和一个容量是 V 的背包每种物品都有无限件可用。
第 i 种物品的体积是 vi价值是 wi。
求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行两个整数 vi,wi用空格隔开分别表示第 i 种物品的体积和价值。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤1000 0vi,wi≤1000
输入样例
4 5
1 2
2 4
3 4
4 5输出样例
10
分析 看分析三重循环才能搞定
优化为二重循环
f[i-1,j-x*v]x*wmax(f[i,j-v]w)
如果 j 大于 v ,f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);
否则 f[i][j]f[i-1][j];
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N10010;int v[N],w[N];
int n,m;
int f[N][N];int main()
{cinnm;for(int i1;in;i) cinv[i]w[i];for(int i1;in;i)for(int j0;jm;j){f[i][j]f[i-1][j];if(jv[i]) f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);}coutf[n][m]endl;return 0;
} 优化为一维
与01背包一样都只用到了一维
但是完全背包表达式中f[i][j]max(f[i][j],f[i][j-v[i]]w[i]);
用到了第i维的状态所以正序枚举 j
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N1010;
int f[N];
int v[N],w[N];int main()
{int n,m;cinnm;for(int i1;in;i) cinv[i]w[i];for(int i1;in;i)for(int jv[i];jm;j){f[j]max(f[j],f[j-v[i]]w[i]);}coutf[m]endl;return 0;}
题目三 多重背包I
有 N种物品和一个容量是 V 的背包。
第 i 种物品最多有 si件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数表示最大价值。
数据范围
0N,V≤100 0vi,wi,si≤100
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例
10
分析 三重循环直接得出结果即可
代码
#include iostream
#include cstring
#include algorithmusing namespace std;
const int N110;
int f[N][N];
int v[N],w[N],s[N];int main()
{int n,m;cinnm;for(int i1;in;i) cinv[i]w[i]s[i];for(int i1;in;i)for(int j0;jm;j)for(int k0;ks[i]k*v[i]j;k){f[i][j]max(f[i][j],f[i-1][j-k*v[i]]k*w[i]);}coutf[n][m]endl;return 0;
}
优化成一维
和01背包优化方式一样
j要倒序枚举
代码
#include iostream
#include algorithm
#include cstringusing namespace std;const int N110;int v,w,s;
int f[N];int main()
{int n,m;cinnm;for(int i1;in;i){cinvws;for(int jm;j1;j--)//看作01背包从后往前枚举for(int k0;ksk*vj;k){f[j]max(f[j],f[j-k*v]k*w);}}coutf[m]endl;return 0;
}
题目四 多重背包II
有 N 种物品和一个容量是 V的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式
第一行两个整数NV用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数表示最大价值。
数据范围
0N≤1000 0V≤2000 0vi,wi,si≤2000
提示
本题考查多重背包的二进制优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例
10分析
本题与前面的区别数据范围变大
不能把一件物品拆成s个当作01背包来解
可以利用二进制的办法把一件物品分成logs件物品然后当作01背包解即可
如果s10,那么可以拆成1 2 4 3 注意最后一个要10-1-2-4得到
这样得到的4件物品科比表示0-10这10件物品
所以本题用到的算法是二进制优化
代码
#include iostream
#include algorithm
#include cstring
#include vectorusing namespace std;const int N2010;
int f[N];int n,m;
int v,w,s;struct goods{int v,w;
};int main()
{cinnm;vectorgoods good;for(int i1;in;i){cinvws;for(int k1;ks;k*2){s-k;good.push_back({v*k,w*k});}if(s0) good.push_back({v*s,w*s});}for(auto g:good){for(int jm;jg.v;j--){f[j]max(f[j],f[j-g.v]g.w);}}coutf[m]endl;return 0;
}
题目五 多重背包III
有 N种物品和一个容量是 V 的背包。
第 i 种物品最多有 si 件每件体积是 vi价值是 wi。
求解将哪些物品装入背包可使物品体积总和不超过背包容量且价值总和最大。 输出最大价值。
输入格式
第一行两个整数NV (0N≤1000,0V≤20000)用空格隔开分别表示物品种数和背包容积。
接下来有 N 行每行三个整数 vi,wi,si用空格隔开分别表示第 i 种物品的体积、价值和数量。
输出格式
输出一个整数表示最大价值。
数据范围
0N≤1000 0V≤20000 0vi,wi,si≤20000
提示
本题考查多重背包的单调队列优化方法。
输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2输出样例
10
分析
本题数据范围更加庞大单单用二进制优化显然不行
根据题意
f(i,j)max(f(i−1,j),f(i−1,j−v)w,⋯,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−(s1)v)sw)
f(i,j−2v)max(f(i−1,j−2v),f(i−1,j−3v)w,⋯,f(i−1,j−(s2)v)sw)
⋯
f(i,rsv)max(f(i−1,rsv),f(i−1,r(s−1)v)w,⋯,f(i−1,r)sw)
f(i,r(s−1)v)max(f(i−1,r(s−1)v),⋯,f(i−1,r)(s−1)w)
⋯
f(i,r2v)max(f(i−1,r2v),f(i−1,rv)w,f(i−1,r)2w)
f(i,rv)max(f(i−1,rv),f(i−1,r)w)
f(i,r)f(i−1,r)
其中 rj mod vi
去掉i-1和w
f(i,r)fr
f(i,rv)max(frv,fr)
f(i,r2v)max(fr2v,frv,fr)
⋯
f(i,r(s−1)v)max(fr(s−1)v,fr(s−2)v,⋯,fr(s−1))
f(i,rsv)max(frsv,fr(s−1)v,⋯,fr) (滑动窗口已满)
f(i,r(s1)v)max(fr(s1)v,frsv,⋯,frv) (滑动窗口已满)
⋯
f(i,j−2v)max(fj−2v,fj−3v,⋯,fj−(s2)v) (滑动窗口已满)
f(i,j−v)max(fj−v,fj−2v,⋯,fj−(s1)v) (滑动窗口已满)
f(i,j)max(fj,fj−v,⋯,fj−sv) (滑动窗口已满)
观察可发现我们要求的始终是一个滑动窗口的最大值
那么我们利用滑动窗口来进行优化
第一重循环枚举每个物品
第二重循环确定有几个滑动窗口由于一个滑动窗口中都是fj−k*v所以每个滑动窗口对v的模值都相同
第三重循环枚举每个滑动窗口求每个滑动窗口中的最大值
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N1010,M20010;
int f[N][M];
int q[M];
int v[M],w[M],s[M];int n,m;int main()
{cinnm;for(int i1;in;i) cinv[i]w[i]s[i];for(int i1;in;i){for(int r0;rv[i];r){int hh0,tt-1;for(int jr;jm;jv[i]){if(hhttq[hh]j-s[i]*v[i]) hh;while(hhttf[i-1][q[tt]](j-q[tt])/v[i]*w[i]f[i-1][j]) tt--;q[tt]j;f[i][j]f[i-1][q[hh]](j-q[hh])/v[i]*w[i];}}}coutf[n][m]endl;
}
观察代码发现只用到了前i-1维的值所以同样可以优化为一维需要备份一下
优化为一维
#include iostream
#include algorithm
#include cstringusing namespace std;const int N1010,M20010;int f[M],g[M];
int v[M],w[M],s[M];
int q[M];
int n,m;int main()
{cinnm;for(int i1;in;i) cinv[i]w[i]s[i];for(int i1;in;i){memcpy(g,f,sizeof f);for(int r0;rv[i];r){int hh0,tt-1;for(int jr;jm;jv[i]){if(hhttq[hh]j-s[i]*v[i]) hh;while(hhttg[q[tt]](j-q[tt])/v[i]*w[i]g[j]) tt--;q[tt]j;f[j]g[q[hh]](j-q[hh])/v[i]*w[i];}}}coutf[m]endl;
}
附滑动窗口模版题
给定一个大小为 n≤106的数组。
有一个大小为 k的滑动窗口它从数组的最左边移动到最右边。
你只能在窗口中看到 k 个数字。
每次滑动窗口向右移动一个位置。
以下是一个例子
该数组为 [1 3 -1 -3 5 3 6 7]k 为 33。
窗口位置最小值最大值[1 3 -1] -3 5 3 6 7-131 [3 -1 -3] 5 3 6 7-331 3 [-1 -3 5] 3 6 7-351 3 -1 [-3 5 3] 6 7-351 3 -1 -3 [5 3 6] 7361 3 -1 -3 5 [3 6 7]37
你的任务是确定滑动窗口位于每个位置时窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数 n 和 k分别代表数组长度和滑动窗口的长度。
第二行有 n 个整数代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出从左至右每个位置滑动窗口中的最小值。
第二行输出从左至右每个位置滑动窗口中的最大值。
输入样例
8 3
1 3 -1 -3 5 3 6 7输出样例
-1 -3 -3 -3 3 3
3 3 5 5 6 7 分析
使用单调队列来求每个窗口中的最大值和最小值
朴素做法每次遍历一遍窗口中的所有值求出对应的最大值和最小值
优化求最大值时如果即将入队的元素大于队尾元素队尾元素删去使得每次入队的元素都是单调递增的从而每次输出队头即得到最大值
滑动窗口的算法步骤是
首先判断队头是否滑出队列
实现每次入队元素递增或者递减
如果遍历到的元素大于滑动窗口大小输出队头即可
代码
#include iostream
#include cstring
#include algorithmusing namespace std;const int N1e65;int n,k;
int q[N];
int a[N];int main()
{cinnk;for(int i0;in;i) cina[i];int hh0,tt-1;for(int i0;in;i){//判断队头是否已经滑出窗口if(hhttq[hh]i-k1) hh;while(hhtta[q[tt]]a[i]) tt--;q[tt]i;if(i-k10) couta[q[hh]] ;}puts();hh0,tt-1;for(int i0;in;i){//判断队头是否已经滑出窗口if(hhttq[hh]i-k1) hh;while(hhtta[q[tt]]a[i]) tt--;q[tt]i;if(i-k10) couta[q[hh]] ;}puts();
}
