【背包题】oj题库

目录

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 的背包。

物品一共有三类：

1. 第一类物品只能用 11 次（01背包）；

2. 第二类物品可以用无限次（完全背包）；

3. 第三类物品最多只能用 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;
}