Acwing2023
2.01背包问题
需求
有 N件物品和一个容量是 V的背包。每件物品只能使用一次。
第 i 件物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 件物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000
0<vi,wi≤10000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
8代码实现
#include <bits/stdc++.h> #include <iostream> using namespace std; const int MAX = 1001; int v[MAX]; int w[MAX]; int dp[MAX][MAX]; //数据范围0-1000 int main() { int n, vo; //number, volume cin >> n >> vo; //输入物品数量和背包容量 for(int i = 1; i <= n; i++) { cin >> v[i] >> w[i]; } //分别输入第i件物品的体积和价值到对应的两个一维数组 dp[0][0] = 0; //选前0件物品，体积限制为0时，可以获得的最大价值为0 for(int i = 1; i <= n; i++) { for(int j = 1; j <= vo; j++) { //先判断当前的体积限制能不能装下当前第i个物品 if(v[i] > j) //当前体积限制为j，第i个物品的体积大于j时，装不下 { dp[i][j] = dp[i-1][j]; } //装不下第i个物品时，当前最大价值等于 当前体积限制(j)时取前i-1个物品时的最大价值 if(v[i] <= j) //可以装下 { dp[i][j] = max(dp[i-1][j], dp[i-1][j-v[i]] + w[i]); } //当前最大价值等于取以下两个价值量的最大值：(当前体积限制下不装此物品的最大价值，当前体积减去第i件物品体积的体积限制下取前i-1件物品的最大价值) } } cout << dp[n][vo]; return 0; }
3.完全背包问题
需求
有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。
第 i种物品的体积是 vi，价值是 wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
输入格式
第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数 vi,wi，用空格隔开，分别表示第 i种物品的体积和价值。
输出格式
输出一个整数，表示最大价值。
数据范围
0<N,V≤10000
0<vi,wi≤10000
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
10代码实现
#include <iostream>
using namespace std;
const int M = 1001;
int dp[M][M]; //动态存放最大价值量
int n, m; //n件物品，背包容量m
int v[M], w[M];
int main()
{
cout << "输入共有几种物品:" << endl;
cin >> n;
cout << "输入背包的容量:" << endl;
cin >> m;
cout << "输入所有物品的体积和价值量:" << endl;
for(int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i];
} //物品共有n件，考虑到有物品0件的情况，此循环i从1开始
for(int i = 1; i <= n; i++) //i为选取前i件物品
{
for(int j = 0; j <= m; j++) //j为当前背包容量
{
for(int k = 0; k*v[i] <= j; k++) //逐渐加大取当前物品的数量，直到装不下
{
dp[i][j] = max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]);
}
}
}
cout << dp[n][m];
return 0;
} /*
f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)
f[i , j-v]= max( f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , .....)
由上两式，可得出如下递推关系：
f[i][j]=max(f[i,j-v]+w , f[i-1][j])
即 f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , .....)这一部分看作f[i, j-v] + w
发现把k消掉了，即计算过程可以优化掉k循环，只需i，j循环
*/
//优化代码：
#include <iostream>
using namespace std;
const int M = 1001;
int dp[M][M]; //动态存放最大价值量
int n, m; //n件物品，背包容量m
int v[M], w[M];
int main()
{
cout << "输入共有几种物品:" << endl;
cin >> n;
cout << "输入背包的容量:" << endl;
cin >> m;
cout << "输入所有物品的体积和价值量:" << endl;
for(int i = 1; i <= n; i++)
{
cin >> v[i] >> w[i];
} //物品共有n件，考虑到有物品0件的情况，此循环i从1开始
for(int i = 1; i <= n; i++) //i为选取前i件物品
{
for(int j = 0; j <= m; j++) //j为当前背包容量
{
dp[i][j] = dp[i-1][j];//先继承取前i-1件物品的最大值，否则初始化值0会影响下面语句的正确执行
if(j-v[i] >= 0)
{
dp[i][j] = max(dp[i][j-v[i]]+w[i], dp[i-1][j]);
} //取前1件物品的价值量随体积的增加慢慢增大，最终达到容量最大时的最优解，再计算取前2件物品的情况...
}
}
cout << dp[n][m];
return 0;
}4167.活动安排
需求
设有 n个活动的集合 E={1,2,…,n}={1,2,…,}其中每个活动都要求使用同一资源，如演讲会场等，而在同一时间内只有一个活动能使用这一资源。
每个活动 i 都有一个要求使用该资源的起始时间 si 和一个结束时间 fi，且 si<fi<。
如果选择了活动 i，则它在时间区间 [si,fi) 内占用资源。
若区间 [si,fi)与区间 [sj,fj)不相交，则称活动 i 与活动 j 是相容的。
也就是说，当 fi≤sj 或 fj≤si时，活动 i 与活动 j 相容。
选择出由互相兼容的活动组成的最大集合。
输入格式
第一行一个整数 n；
接下来的 n 行，每行两个整数 si 和 fi。
输出格式
输出互相兼容的最大活动个数。
数据范围
1≤n≤1000
输入样例：
4
1 3
4 6
2 5
1 7
输出样例：
2代码实现
#include <stdio.h>
#include <bits/stdc++.h>
using namespace std;
const int MAX = 1005;
struct work
{
int left;
int right;
}w[MAX]; //存放一个活动的开始和结束时间
//贪心选择:活动的结束时间，越早结束下一个活动的开启时间越早，对应能装下的总活动最多
bool cmp(work a, work b)
{
return a.right < b.right;
}
int n; //活动的数量
int cnt = 0; //最后选中的活动数量
int now = 0; //存放当前活动的下标
int main()
{
cout << "请输入活动的数量：" << endl;
cin >> n;
cout << "请输入每个活动的开始和结束时间" << endl;
for(int i = 1; i <= n; i++)
{
cin >> w[i].left >> w[i].right;
} //初始化数据
sort(w+1,w+1+n,cmp);
for(int i = 1; i <=n ;i++)
{
if(w[i].left >= w[now].right)
{
cnt++; //为了保证cnt的正确，now的初始值应该赋0而不是1，否则会少算第一个活动的值导致最后结果少1
now = i;
}
}
cout << "最多可以进行" << cnt << "个活动" << endl;
return 0;
}