目录
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;
}
