目录
1282 - 简单背包问题
1780 - 采灵芝
1888 - 多重背包(1)编辑
1891 - 开心的金明
2073 - 码头的集装箱
1905 - 混合背包
1282 - 简单背包问题
#include <bits/stdc++.h>
using namespace std;
//二维数组:dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])
//一维数组滚动优化:
//状态转移方程:dp[j]=max(dp[j],v[i]+dp[j-w[i]])
int w;//背包容量
int dp[20010];
int n,wi,vi;int main() {cin>>w>>n;//遍历每个物品for(int i=1; i <= n; i++) {cin>>wi>>vi;
//倒过来循环for(int j=w; j>= wi; j--) {
//讨论每个物品选和不选的两个状态
//取能到的价值的最大值dp[j]= max(dp[j],dp[j-wi]+ vi);}}cout<<dp[w];return 0;
}
#include <bits/stdc++.h>
using namespace std;//动态转移方程:dp[i][j]=max(dp[i-1][j],v[i]+dp[i-1][j-w[i]])
//c:代表背包容量
//dp[i][j]:有i件物品,背包容量为了的情况下存储的最大价值
int c,dp[110][20100],w[110],v[110],i,j,n;
int main() {
//读入cin>>c>>n;for(i =1; i<= n; i++) {cin>>w[i]>>v[i];}//递推求 dp 数组//i:代表物品数量for(i = 1; i <= n; i++) {//在i件物品,讨论背包容量分别是1~c的情况下,最大价值//j:代表背包容量for(j= 1; j<= c; j++) {//如果能放得下if(w[i]<= j) {dp[i][j]= max(dp[i-1][j],v[i]+dp[i-1][j-w[i]]);} else {//放不下dp[i][j]= dp[i-1][j];}}}//输出n件物品,背包容量为c的最大价值cout<<dp[n][c];return 0;
}
1780 - 采灵芝
#include <bits/stdc++.h>
using namespace std;/*完全背包状态转移方程
二维写法:f[i][j]= max(f[i-1]], f[i][j-w[i]]+v[])
一维写法:f[]j=max(f[j],f-w[i]]+v[i])
一维状态转义方程和01背包一致,要注意,完全背包要从前往后推导。*/
int t,m;
int f[100010];
int ti,vi;//每个物品的采摘时间和价值
int main() {cin>>t>>m;//读入m个物品 for(int i = 1; i<= m; i++) {cin>>ti>>vi;//正序循环
//从当前物品的重量(采摘时间)~背包容量最大时间)循环for(int j = ti; j <= t; j++) {f[j] = max(f[j],f[j-ti]+vi);}}cout<<f[t];//背包能够存储的最大价值return 0;
}
1888 - 多重背包(1)
#include <bits/stdc++.h>
using namespace std;
/*01背包:每种物品有1件
完全背包:每种物品有无限件数多
重背包:每种物品有Si件
解题思路:将多重背包转换为01背包
将si件物品都存起来,转换为有si个物品,每个物品有1件*/
int n,c;//c背包容量
int v[10010],w[10010];
int dp[110];
int vi,wi,si,k;//k代表数组下标
int main() {cin>>n>>c;for(int i=1; i <= n; i++) {cin>>vi>>wi>>si;//第i个物品有si件,都存入数组for(int j=1; j<= si; j++) {k++;v[k]= vi;w[k]= wi;}}
//01 背包for(int i=1; i <= k; i++) { //逆序从背包容量循环到当前物品体积for(int j=c; j >= v[i]; j--) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[c];return 0;
}
#include <bits/stdc++.h>
using namespace std;
/*01背包:每种物品有1件
完全背包:每种物品有无限件数多
重背包:每种物品有Si件
解题思路:将多重背包转换为01背包
将si件物品都存起来,转换为有si个物品,每个物品有1件*/
int n,c;//c背包容量
int v[110],w[110],s[110];
int dp[110];int main() {cin>>n>>c;for(int i=1; i <= n; i++) {cin>>v[i]>>w[i]>>s[i];//第i个物品有si件,都存入数组}
//01 背包
//有n个物品for(int i=1; i<= n; i++) {for(int k=1; k<= s[i]; k++) {//逆序从背包容量循环到当前物品体积for(int j=c; j>= v[i]; j--) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}}}
// for(int i=1; i <= k; i++) {
// //逆序从背包容量循环到当前物品体积
// for(int j=c; j >= v[i]; j--) {
// dp[j]= max(dp[j],dp[j-v[i]]+w[i]);
// }
// }cout<<dp[c];return 0;
}
1891 - 开心的金明
题目描述
金明今天很开心,家里购置的新房就要领钥匙了,新房里有一间他自己专用的很宽敞的房间。更让他高兴的是,妈妈昨天对他说:“你的房间需要购买哪些物品,怎么布置,你说了算,只要不超过NN元钱就行”。今天一早金明就开始做预算,但是他想买的东西太多了,肯定会超过妈妈限定的NN元。于是,他把每件物品规定了一个重要度,分为55等:用整数1-51−5表示,第55等最重要。他还从因特网上查到了每件物品的价格(都是整数元)。他希望在不超过NN元(可以等于NN元)的前提下,使每件物品的价格与重要度的乘积的总和最大。
设第jj件物品的价格为v[j]v[j],重要度为w[j]w[j],共选中了kk件物品,编号依次为j_1,j_2,…,j_kj1,j2,…,jk,则所求的总和为:
v[j_1] \times w[j_1]+v[j_2] \times w[j_2]+ …+v[j_k] \times w[j_k]v[j1]×w[j1]+v[j2]×w[j2]+…+v[jk]×w[jk]。
请你帮助金明设计一个满足要求的购物单。
#include <bits/stdc++.h>
using namespace std;int w[30],v[30],f[50000];
//w数组为重要度,v数组为money,f是用来dp的数组
int n,m;//n是总物品个数,m是总钱数
int main() {cin>>m>>n;//输入for(int i=1; i<=n; i++) {cin>>v[i]>>w[i];w[i]*=v[i];//v数组在这里意义变为总收获(重要度*money)}
//01背包(参照第二类模板“一维数组优化”for(int i=1; i<=n; i++) {for(int j=m; j>=v[i]; j--) {
//注意从m开始if(j>=v[i]) {f[j]=max(f[j],f[j-v[i]]+w[i]);//dp}}}cout<<f[m]<<endl;//背包大小为m时最大值return 0;
}
2073 - 码头的集装箱
题目描述
码头上停泊一艘远洋轮船,轮船可以装下 cc 吨的货物,码头上有 nn 个集装箱需要运走,已知第 ii 个集装箱的重量为w_iwi。
请你编程计算,在不超出轮船最大载重量的情况下,该轮船最多可以运走多少吨的集装箱。(注意:单个集装箱不能拆开运送,对于每个集装箱来说,要么整个运到轮船上,要么不运)
#include <bits/stdc++.h>
using namespace std;int n,c,w;
int f[40000];
int main() {cin>>n>>c;for(int i = 1; i <= n; i++) {cin>>w;for(int j=c; j>=w; j--) {f[j] = max(f[j],f[j-w]+w);}}cout<<f[c];
return 0;
}
1905 - 混合背包
题目描述
有 NN 种物品和一个容量是 VV 的背包。
物品一共有三类:
-
第一类物品只能用 11 次(01背包);
-
第二类物品可以用无限次(完全背包);
-
第三类物品最多只能用 s_isi 次(多重背包);
每种体积是 v_ivi,价值是 w_iwi。
求解将哪些物品装入背包,可使物品体积总和不超过背包容量,且价值总和最大。
输出最大价值。
#include <bits/stdc++.h>
using namespace std;
const int N=20000;
int v[N],w[N],s[N];
int vi,wi,si;
int k=0;//表示存入数组的数据量
int dp[1010];
int n,m;
int main() {cin>>n>>m;for(int i=1; i<= n; i++) {cin>>vi>>wi>>si;//如果是多重背包,做二进制拆分if(si > 0) {int t=1;while(t<= si) {k++;w[k]= t * wi;v[k]= t * vi;s[k]=-1;//转换为 01 背包si= si -t;t= t * 2;}if(si >0) {k++;w[k]= si * wi;v[k]= si * vi;s[k]=-1;//01背包}} else {k++;w[k]= wi;v[k]= vi;s[k]= si;}}
//计算//循环k个物品for(int i=1; i<= k; i++) { //判断是01背包还是完全背包if(s[i]== -1) {for(int j= m; j >= v[i]; j--) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}} else {for(int j = v[i]; j<= m; j++) {dp[j]= max(dp[j],dp[j-v[i]]+w[i]);}}}cout<<dp[m];return 0;
}