【背包题】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;
}