19185 01背包问题
1. 题面
一个旅行者有一个最多能装 M公斤的背包，现在有 n件物品，它们的重量分别是W1，W2，...,。
它们的价值分别为C1,C2,...,，求旅行者在不超过背包重量M的情况下，能获得最大总价值。
PS：01背包问题也能用于个人的时间管理，如何分配时间在不同的任务上，才能最大化提升个人价值。输入格式
第一行：两个整数，M(背包容量，M<=200)和N(物品数量，N<=30)；
第2..N+1行：每行二个整数Wi，Ci，表示每个物品的重量和价值。2. 解题思路
这道题是经典的动态规范问题，其特征是涉及到状态和选择
对于这道题而言，我们依照动态规划三部曲进行分析
- 状态是什么?
如果我们将地上的物品看作是一个个的，我们的背包从左走到右，这时候不断变化的状态就是我们走到了第i个物品前方。然后如果我们选择将物品装入包中，这时候不断变化的状态就是我们的背包的剩余容量。
- 选择是什么?
选择就是当我们走到一个物品的前面，我们可以将其装入背包，也可以选择不将其装入背包，这就是选择
- 怎么来定义dp数组?
dp数组的定义与状态量有关，一般来说，有几个状态，我们的dp数组就有几维。
根据状态分析，我们可以这样定义dp数组
int n;//可挑选物品的个数
int m;//背包的容量
int[][] dp = new int[n][m];
//dp[i][j]:对于前i个物品,当前背包的容量为j,这时候所能够得到的价值为dp[i][j]
//dp[n][m]:对于前n个物品,当前背包容量为m,这时候所能得到的价值为dp[n][m]
...
return dp[n][m];- 状态转移方程怎么写?
状态转移方程是数学递推的过程，其特点是从一般到特殊，因此是我们先写出base-case，然后根据dp-table来写出遍历方向。
base-case:
//当对于前0个物品的时候,这时候根本没有物品可以选,所以肯定价值是0
for(int i = 0;i<m;i++){
dp[0][i] = 0;
}
//对于背包容量为0的时候,这时候根本放不下物品,所以肯定价值是0
for(int j = 0;j<n;j++){
dp[j][0] = 0;
}初始化后的dp-table:
如图所示，经过base-case之后，dp-table就变成了这样，这将会是我们后续推导遍历方向的重要依据
其中打钩的地方代表已知,其他表示未知
现在来思考一下状态是如何转移的?
一般来说,
状态转移依赖于选择。
- 当我们走到
i位置的时候,我们可以选择将i物品装入包中,前提是包有足够空间- 或者是不将
i物品装入包中。
//将第i件物品装入包中
if(j-w[i-1]>=0){//包中有足够空间
dp[i][j-w[i-1]] = dp[i-1][j]+v[i-1];
//如果我们将这个物品装入包中,那么当前的收益就是选择前i-1个物品,而且背包容量为j的时候最大收益加上再装一个物品 的收益
}//不将第i个物品放入包中
dp[i][j] = dp[i-1][j];
//不把这个物品放入包中,那么就会继承之前选择i-1个物品时,而且背包容量为j的最大收益通过上面的分析
我们知道
dp[i][j]依赖于dp[i-1][...]的结果,也就是依赖于上一行的计算结果，…是表示这一行所需要的下标是不确定的，因此我们需要计算出一整行数据。
for(int i = 1;i <= n;i++){//选择前i个物品,i∈[1,n]
for(int j = 1;j <= m;j++){//背包容量为j,j∈[1,m],计算每一行
if(j-w[i-1] < 0){
//只能选择
dp[i][j] = dp[i-1][j];
continue;
}
dp[i][j] = Math.max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
}
}至此,这道题的核心就全部分析出来了,接下来就是编码检验
3. AC代码
//
// Created by 12743 on 2022/10/7.
//
#include <iostream>
const int N = 30+5;
const int M = 200+5;
int dp[N][M];
int w[M];
int v[N];
using namespace std;
class Solution {
public:
void solve(){
int m,n;cin>>m>>n;
//base-case
for(int i = 0;i < n;i++){
cin>>w[i];cin>>v[i];
}
for(int i = 0;i <= n;i++){
dp[i][0] = 0;
}
for(int j = 0;j <= m;j++){
dp[0][j] = 0;
}
//状态转移
for(int i =1;i <= n;i++){
for(int j=1 ;j <= m;j++){
if(j- w[i-1] <0){
dp[i][j] = dp[i-1][j];
continue;
}
dp[i][j] = std::max(dp[i-1][j],dp[i-1][j-w[i-1]]+v[i-1]);
}
}
cout<<dp[n][m]<<endl;
}
};
int main(){
ios::sync_with_stdio(false);
Solution solution;
solution.solve();
return 0;
}18708 最大子段和
1. 题面
一个整数序列，选出其中连续且非空的一段使得这段和最大。
注意当题目要求输入输出的数据量很大时，尽量使用scanf和printf。 c++提供的cin和cout速度比较慢，有可能在读取数据和输出数据时导致超时。
第一行是一个正整数N，表示了序列的长度（0=<N<=200000）。
第二行包含N个绝对值不大于10000的整数ai。一个整数，为最大的子段和。子段的最小长度为1。数据确保结果在类型int范围内。
7
2 -4 3 -1 2 -4 3
42. 题目分析
首先我们来思考一下暴力解，首先理解一下什么叫子数组:子数组是连续的，也就是从[i,j]一段连续的数组和，那么如果我们能够得到所有的[i,j]区间的和，并且进行比较迭代的话就可以解出这道题。
//求解前缀和
int n = nums.length;
//前i个数的和
int[] preSum = new int[n+1];
preSum[0] = 0;
for(int i = 1;i<=n;i++){
preSum[i] = preSum[i-1]+nums[i-1];
}
int max = Integer.MIN_VALUE;
for(int i = 0;i<n;i++){
for(int j = i;j<n;j++){
max = Math.max(max,preSum[j]-preSum[i]);
}
}
return max;思考一下时间复杂度
对于两层for循环而言，肯定是n方的复杂度了，然后题目给的样例是2e5, n方的算法将会超时。
那么就要考虑优化了。
一般来说,优化无非就是剪枝，或者用备忘录来减少重复计算的时间
从题目的计算逻辑，我们在计算[i,j]的最大子数组和的时候，其[0...i-1]中的最大子数组和已经求出来了。
根据求和的性质，我们要求一个和的最大值，那么这个和的最大值肯定是在之前某一段的最大值，加上当前的值求出来的。
- 状态:当前遍历到的第
i个元素 - 选择:是否将当前遍历到的第
i个元素与前面的子数组连成一个形成子数组和
我们可以这样来定义dp数组，dp[i]:以nums[i]为结尾的最大子数组的和，这样定义的原因是:
子数组的连续的，如果我们想要求出一个最大子数组，肯定是之前的一个最大子数组，加上后边的那一个数，这样就能够很好的完成递推。
int[] dp = new int[n];
//base-case
//注意,如果题目说:子段和可以为空,那么这时候dp[i]的初始化可以为0(当nums[i]为负数的时候)
for(int i = 0;i<n;i++){
dp[i] = nums[i];
}
int maxIndex = 0;
for(int i = 1;i<n;i++){
dp[i] = Math.max(dp[i-1]+nums[i],nums[i]);
if(dp[i-1]+nums[i] > nums[i]){
dp[i] = dp[i]+nums[i];
maxIndex = i;
}
}
return dp[maxIndex];3.AC代码
//
// Created by 12743 on 2022/10/7.
//
#include <iostream>
using namespace std;
class Solution {
public:
const static int N = 200000;
int nums[N];
int dp[N];
void solve(){
int n;cin>>n;
for(int i = 0;i<n;i++){
cin>>nums[i];
dp[i] = nums[i];
}
int maxIndex = 0;
for(int i = 1;i<n;i++){
//nums[i]<dp[i-1]+nums[i]
if(dp[i-1]>0){
dp[i] = dp[i-1]+nums[i];
}
if(dp[i] > dp[maxIndex]){
maxIndex = i;
}
}
cout<<dp[maxIndex]<<endl;
}
};
int main(){
ios::sync_with_stdio(false);
Solution solution;
solution.solve();
return 0;
}
11080 游泳圈的最大子矩阵和
1. 题面
二维数组首尾相连，上下也相连，像个游泳圈或轮胎，又如何求最大子矩阵和？
如游泳圈展开成3行3列的二维矩阵：
-18 10 7
1 -20 2
1 38 -2
那么最大的子矩阵和为：10+7+38-2=53
若：
3 3
2 10 7
1 -20 2
1 38 -2
那么最大的子矩阵和为：10+7+2+38-2+1=56
提示:
1）先编写一维环形（一圈的形状）长度为len的数据中的最大子段和，且子段长不超过n。
————注意要先调试通过这个程序段，要小心编写，用书上动态规划那段程序修改的话
比较麻烦且易出错，用简单算法改倒是很容易做到的。
2）将游泳圈水平方向上扩展n-1列，垂直方向上扩展m-1行，形成2m-1行2n-1列的扩展矩阵，
在扩展矩阵上求解最大不超过m*n的最大矩阵和。2. 解题思路
首先分析一下题面，题目要求的是求解一个最大子矩阵和，一个最简单的想法就是枚举所有的子矩阵和，也就 是说从(0,0)->(n,m)这个矩阵中的所有子矩阵,取最大值就可以了。
但是其实来分析一下，是否有必要每次都枚举计算每个子矩阵呢?如果我已经计算出了某个范围的子数组，那么我能不能复用它，然后用它来计算新的最大值呢?
- 能不能贪心?
根据上面的分析，我们会有一个直观的想法，就是在扩大子矩阵规模的时候，考察扩大的子矩阵后的和是否会比原来的子矩阵和会更大，这样的想法看似是正确的，但是其实这会导致漏解。
为什么呢？这是因为我们知道子矩阵是一定范围内连续的，如果我们没有选择某一部分的元素，那么与其相连的其他元素就不能被选择了。
理解:
比如说我选择了
nums[0][0]到nums[3][3]为我们的子矩阵，然后我们想要扩大规模成nums[0][0]到nums[4][4]，但是我们不选，因为这时候扩大了之后变小了，但是要注意，一旦做出了这个选择，之后的nums[0][0]到nums[5...n][5..n]的子矩阵就永远不可能被计算到了，而有没有可能之后的值是更大的呢?是完全有可能的。
因此这样的话，我们就了解到了，子矩阵的和是和上一次计算的状态相关的，因此简单的贪心不能得到正确的答案。那么由于提到了选择、状态，那么大概率就要上动态规划了
3. 解题过程
这道题比较复杂，但是对于二维的问题而言，我们有一个常规的做法就是降维，我们先从一维的角度去理解这个问题。
一维子数组的最大和
具体的解法见上文，这里的话只提出关键的思路来过渡
对于一维而言，我们求解的是以
nums[i]结尾的最大子数组和那么对于二维而言，如果我们想要
降维，一个常见的手段就是定一议二。我们知道子矩阵是由行列上的元素组成的。
对于任意的一个子矩阵，其被取得行是
[i,j]，也就是从第i行到第j行的元素，以下面这个矩阵为例[1] [2] [3] [1] -18 10 7 [2] 1 -20 2 [3] 1 38 -2如果我们想要得到所有的矩阵，那么就要取遍
[i,j]内的所有的行组合，其中i∈[0,n-1],j∈[i,n-1]如果我们定下来了行，那么我们只需要选定列就可以枚举出所有的矩阵了。
同理，我们要取遍
[k,z]内所有的列组合，其中k∈[0,m-1],z∈[k,m-1]最后就是求和的阶段，求和的过程要求我们求和
[i,j]这些行内的[k,z]的和最后将每一列的和列成一个一维数组，转为一维的最大子数组和即可求解。
对于这道题而言，还有一个难点就是有环
环的解决
一般来说，环的解决办法有两种
- 对于数据量不大的情景，可以使用拼接数据的方法，模拟这个环，优点是直观，清晰易懂，但是有额外的开销，但可以几乎不计
for(int i = n;i< 2*n-1;i++){ for(int j = 0;j<2*m-1;j++){ nums[i][j] = nums[i%n][j%m]; } }
- 对于数据量大的情景，可以使用取模的方法来对指针进行重置，同时限定边界，优点是没有额外的开销，空间复杂度最优。但是就是容易写错。
至此，整道题的核心就已经分析完了，详细的请看通过的代码示例
4. AC代码
//
// Created by 12743 on 2022/10/7.
//
#include <iostream>
#include <cstring>
using namespace std;
class Solution {
public:
const static int N = 100+5;
const static int M = 100+5;
int dp[M];
int nums[N][M];
int memo[N][M];
int preSum[N][M];
void solve(){
int n,m;cin>>n>>m;
memset(preSum,0,sizeof preSum);
for(int i = 1;i<=n;i++){
for(int j = 1;j<=m;j++){
cin>>nums[i][j];
nums[n+i][j] = nums[i][j];
nums[n+i][m+j] = nums[i][j];
nums[i][j+m] = nums[i][j];
}
}
for(int i = 1;i<=2*n;i++){
for(int j = 1;j<=2*m;j++){
preSum[i][j] = preSum[i-1][j]+nums[i][j];
}
}
/*
//debug here pass
for(int i = 1;i <= 2*n;i++){
for(int j = 1;j<=2*m;j++){
cout<<nums[i][j]<<" ";
}
cout<<endl;
}
cout<<endl;
for(int i = 1;i <= 2*n;i++){
for(int j = 1;j <= 2*m;j++){
cout<<preSum[i][j]<<" ";
}
cout<<endl;
}
*/
int Max = -2147483648;
for(int i = 1;i <=n;i++){
for(int j = 0;j < n;j++){
memset(dp,0,sizeof dp);
for(int k =1;k<=m;k++){
//base-case
for(int z = 0;z<m;z++){
dp[z] = preSum[i+j][k+z]-preSum[i-1][k+z];
}
for(int z = 1;z<m;z++){
if(dp[z-1] >0){
dp[z] = dp[z-1]+preSum[i+j][k+z]-preSum[i-1][k+z];
}
Max = std::max(Max,dp[z]);
}
}
}
}
cout<<Max<<endl;
}
};
int main(){
ios::sync_with_stdio(false);
Solution solution;
solution.solve();
return 0;
}
