动态规划
动态规划概论
楼梯
这给定一座有10级台阶的楼梯，我们要从下往上走，每跨一步只能向上走1级或者2级台阶，请问
一共有多少种走法呢？
方法1：搜索，我们写个dfs，依次枚举每一步向上走多少台阶，最后统计有多少可行的方案。
如果要走100级台阶，搜索一年都不一定能搜索出来
方法2：组合数学
我们先把走法的表示方式简化：
用一个只包含1和2的序列表示从下到上每一步分别走了几级台阶;
22222表示一共走了5步，每次走2级台阶，这是一种有效的走法;
1111222表示一共走了7步，前四步走1级台阶，后三步走2级台阶，这也是有效的走法。接着枚举一共有几步走了2级台阶，就能算出有几步走了1级台阶，最后可以用组合数学算。
10=10*1（10个1，共C(10,10)=1种)
=8*1+2（8个1,1个2，共C(9,8）=9种）
=6*1+2*2（6个1，2个2，共C(8，6)=28种）
=4*1+3*2（4个1，3个2，共C(7，4)=35种）
=2*1+4*2(2个1，4个2，共C(6，2)=15种）
=5*2（5个2，共C(5，5)=1种）
共计1+9+28+35+15+1=89种。
方法3：递归
考虑最后一步的情况，我们只能从第9级或者第8级走过去。不管走到第8级和第9级的过程，
如果我们知道走到第8级的走法共有x种，走到第9级的走法有y种，那么走到第10级的走法呢？
这一共有x+y种!
我们把走到i级台阶的走法数量用f(i）来表示，有f(10)=f(8)+f(9)
同理有f(9)=f(7)+f(8)，f(8)=f(6)+f(7)
对于任意的n≥2，有f(n)=f(n-2)+f(n-1)。（其实就是个斐波那契）
方法4 动态规划
递归计算会出现很多的重复计算
用动态规划就可以解决这个问题，从头开始推，由小问题的最优推出大问题的最优
#include <bits/stdc++.h>
using namespace std;
int n;
long long f[51];
int main()
{
cin>>n;
f[0]=1;f[1]=1;
for(int i=2;i<=n;i++)
{
f[i]=f[i-1]+f[i-2];
}
cout<<f[n];
return 0;
}
最短路
#include <bits/stdc++.h>
using namespace std;
int a[1001][1001],f[1001],n,m;
int main()
{
cin>>n>>m;
memset(a,127,sizeof a);
for(int i=1;i<=m;i++)
{
int x,y,z;
cin>>x>>y>>z;
a[x][y]=min(a[x][y],z);
}
memset(f,127,sizeof(f));
f[1]=0;
for(int i=2;i<=n;i++)
{
for(int j=1;j<i;j++)
{
if(f[j]<1<<30&&a[j][i]<1<<30)
{
f[i]=min(f[i],f[i]+a[j][i]);
}
}
}
cout<<f[n];
return 0;
}
最长上升子序列（LIS)
#include <bits/stdc++.h>
using namespace std;
int n,a[1001],f[1001];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++)
{
if(a[j]<a[i])
{
f[i]=max(f[i],f[j]+1);
}
}
}
int ans=0;
for(int i=1;i<=n;i++)
{
ans=max(ans,f[i]);
}
cout<<ans;
return 0;
}
最长公共子序列（LCS)
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1001],b[1001],f[1001][1001];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
cin>>b[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])
{
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
}
cout<<f[n][m];
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n,m,a[1001],b[1001],f[1001][1001];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=m;i++)
{
cin>>b[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j])
{
f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
}
}
cout<<f[n][m];
return 0;
}
最长回文子串
传送门
给定一个字符串，请你求出其中的最长回文子串的长度。
例如，给定字符串 Is PAT&TAP symmetric?，最长回文子串为 s PAT&TAP s，其长度是 11 11 11。
输入格式
包含一个非空字符串。
输出格式
输出一个整数，表示给定字符串的最长回文子串的长度。
数据范围
给定字符串的长度不超过 1000 1000 1000。
输入样例：
Is PAT&TAP symmetric?
输出样例：
11
方法1
由于回文串是对称的，所以我们可以枚举所有的中点，再向两侧扩散，时间复杂度为O（n^2）。
//中点扩散算法
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int dp[N][N];
int main()
{
string str;
getline(cin,str);
int res=0;
for(int i=0;i<str.length();i++)
{
int l=i-1,r=i+1;//判断奇数长度回文串
while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;
res=max(res,r-l-1);
l=i,r=i+1;//判断偶数长度回文串
while(l>=0&&r<str.length()&&str[l]==str[r]) l--,r++;
res=max(res,r-l-1);
}
cout<<res<<endl;
return 0;
}
方法2 动态规划
用动态规划来做上面的那个例题，dp[N][N]来存状态，dp[ i] [ j ]=1,表示字符串从i到j为回文串。
（1）当str[ i ]==str[ j ]时，dp[i+1][j-1]=1,则dp[ i ][ j ]=1 ( [i+1,j-1]为回文串，且str[ i ]==str[ j ]则[i,j]为回文串 ),否则dp[ i ][ j ]=0。
（2）当str[ i ]!=str[ j ]时,dp[ i ][ j ]=0。
在遍历方面也要注意，如果按照i和j从小到大的顺序来枚举子串的两个端点,然后更新dp[i]lj],会无法保证dp[i + 1][ - 1]已经被计算过,从而无法得到正确的dp[i][i]。我们可以遍历长度，长度从小到达依次增加，每次判断出左右端点即可。
//动态规划
#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
bool dp[N][N];
int main()
{
string str;
getline(cin,str);//读入字符串
int res=1;
int n=str.length();
for(int i=0;i<n;i++)
{
dp[i][i]=true;
if(i<n-1&&str[i]==str[i+1])//判断边界条件
{
res=2;
dp[i][i+1]=true;
}
}
for(int l=3;l<=n;l++)//遍历字符串长度，最小从3开始（最小为1，加上左右两边）
{
for(int i=0;i+l-1<n;i++)//左边界
{
int j=i+l-1;//右边界
if(str[i]==str[j]&&dp[i+1][j-1])
{
dp[i][j]=1;
res=l;//更新时，一定l>=res
}
}
}
cout<<res<<endl;
return 0;
}
概率动态规划
用f[x]表示能走到x号城市的概率,那么f[1]=1
从x城走到y城概率f[y]+=f[x]/d[x]
其中d[x]表示从x号城市出发的高速公路有多少条
对于每个节点 i，将节点 i 的概率 f[i] 均分给它的每个邻接节点 c[i][j]，并且将这一部分概率累加到 f[c[i][j]] 中。
i = 2，c[2] = {3, 4, 5}，即从节点 2 出发，有边指向节点 3、4、5。
f[2] = 0.6，表示从节点 1 到节点 2 的概率为 0.6。
l = 3，即节点 2 有 3 个邻居（3、4、5）。
f[3] += f[2] / 3; // f[3] 增加 0.6 / 3 = 0.2
f[4] += f[2] / 3; // f[4] 增加 0.6 / 3 = 0.2
f[5] += f[2] / 3; // f[5] 增加 0.6 / 3 = 0.2
#include <bits/stdc++.h>
using namesapace std;
int n,m;
vector<int> c[101];
double f[101];
int main()
{
cin>>n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
cin>>x>>y;
c[x].push_back(y);
}
memset(f,0,sizeof (f));
f[1]=1;
for(int i=1;i<n;i++)
{
int l=c[i].size();
for(int j=0;j<l;j++)//边界条件不使用c[i].size,因为这是o(n)的复杂度
{
f[c[i][j]]+=f[i]/l;
}
}
return 0;
}
区间动态规划
石子合并
递归
#include <bits/stdc++.h>
using namespace std;
int n,a[501],s[501];
int solve(int l,int r)
{
if(l==r)
{
return 0;
}
int ans=1<<30;
for(int m=l;m<r;m++)
{
ans=min(ans,solve(l,m)+solve(m+1,r));
}
return ans+s[r]-s[l-1];
}
int main()
{
cin>>n;
for(int i=l;i<=n;i++)
{
cin>>a[i];
}
for(int i=l;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
cout<<solve(1,n);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n,a[501],s[501],f[501][501];
int solve(int l,int r)
{
if(f[l][r]!=-1)
{
return f[l][r];
}
if(l==r)
{
return f[l][r]=0;
}
int ans=1<<30;
for(int m=l;m<r;m++)
{
ans=min(ans,solve(l,m)+solve(m+1,r));
}
return ans+s[r]-s[l-1];
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
memset(f,255,sizeof f);
cout<<solve(1,n);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
int n,a[501],s[501],f[501][501];
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
s[i]=s[i-1]+a[i];
}
memset(f,127,sizeof(f));
for(int i=1;i<=n;i++)
{
f[i][i]=0;
}
for(int i=1;i<n;i++)
{
for(int j=1;j<=n-i;j++)
{
for(int k=j;k<j+i;k++)
{
f[j][j+i]=min(f[j][j+i],f[j][k]+f[k+1][j+i]+s[j+i]-s[j-1]);
}
}
}
cout<<f[1][n];
return 0;
}
括号序列
#include <bits/stdc++.h> // 包含常用的头文件，如 iostream, vector, algorithm 等
using namespace std;
int n, f[501][501]; // n: 括号序列的长度，f: 动态规划表，f[i][j] 表示从第 i 个括号到第 j 个括号的最大有效匹配括号对数
char str[511]; // 存储括号序列，大小为 511 是为了容纳括号序列及其编号从 1 开始（数组下标从 1 开始）
int main()
{
scanf("%d%s", &n, str + 1); // 读取括号序列的长度 n 和括号序列字符串 str，从 str[1] 开始存储
memset(f, 0, sizeof(f)); // 初始化 f 数组为 0，表示所有区间的最大匹配括号对数初始为 0
// 遍历每个可能的子序列长度 i
for (int i = 1; i < n; i++) { // i 表示当前子序列的长度，遍历从 1 到 n-1
// 遍历子序列的起始位置 j，j 表示当前子序列的起始位置
for (int j = 1; j <= n - i; j++) { // j 表示起始位置，保证子序列长度为 i，不越界
// 处理括号匹配的情况：首先检查是否是括号对 '()' 或 '[]' 的情况
if ((str[j] == '(' && str[j + 1] == ')') || (str[j] == '[' && str[j + i] == ']')) {
// 如果当前括号是匹配的括号对，则更新动态规划表
f[j][j + i] = f[j + 1][j + i - 1] + 2; // 当前匹配对加上内层匹配的得分
}
// 对于每个可能的分割点 k，尝试分割子串来更新最优解
for (int k = j; k < j + i; k++) { // k 是分割点，遍历 [j, j+i] 区间的所有可能分割
// f[j][j+i] 表示从 j 到 j+i 的最大匹配括号对数
f[j][j + i] = max(f[j][j + i], f[j][k] + f[k + 1][j + i]);
// 计算通过分割子串 [j, k] 和 [k+1, j+i] 的最大得分
}
}
}
cout << f[1][n]; // 输出最终从 1 到 n 的最大有效括号对数
return 0;
}
石子合并（环形）
然后这也是一个非常经典的套路，就是我们这种圈的情况，我们就把它连成两倍，然后再连成两倍上面做，然后最后就是考虑f(1)(n)考虑f(2)(n+1)。就是圆圈的情况，很多情况下都是可以这样做，其实你就会把每一条边删掉，以后情况你都能够考虑进去。就f(1)(n)就是考虑的是1到n的那条边删掉情况f(2) (n+1)就是2到那个n+1的那条边删掉情况f(3)到(n+2)就是3到1的那条边被删掉情况，你就能把所有情况。情况都考虑完。那么，这个事情复杂度就变成了n3方大,就是你会发现你把它倍增以后，就你把它一模一样，后面屁股上又接上去了，以后你n3方做完以后你就把删除，每条边的情况你都已经考虑到。
这段代码是动态规划的核心部分，目的是计算合并石子堆时最小的得分。这里 i 表示子序列的长度，而 f 数组用来存储从堆 j 到堆 j + i 的最小合并得分。
代码分析：
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n - i; j++) {
for (int k = j; k < j + i; k++) {
f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);
}
}
}
外层循环：
for (int i = 1; i <= n; i++)i表示当前子问题的长度，即正在考虑的子序列的长度。i从1到n，依次表示从长度为 1 的子序列到长度为n的子序列。
中层循环：
for (int j = 1; j <= n - i; j++)j是当前子序列的起始位置，表示从位置j开始，长度为i的子序列。- 由于
j和i决定了子序列的末尾位置j + i，为了避免数组越界，j最大值为n - i。
内层循环：
for (int k = j; k < j + i; k++)k用于在当前子序列[j, j + i]中选择一个分割点。- 子序列
a[j...j + i]被划分为两部分：一部分是a[j...k]，另一部分是a[k+1...j + i]，并且k需要遍历整个子序列。
状态转移：
f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);- 这是动态规划的状态转移公式。
f[j][j + i]表示将子序列a[j...j + i]合并成一堆的最小得分。- 递推关系：选择一个分割点
k，计算两部分的最小得分f[j][k]和f[k + 1][j + i]，加上合并这两部分的得分（即合并后的石子数），合并后的得分是s[j + i] - s[j - 1]，即从位置j到j + i这一部分的总石子数。 - 通过遍历所有可能的分割点
k，我们可以得到从j到j + i的最小得分。
具体举例：
假设我们有 4 堆石子，堆的石子数分别为 [a1, a2, a3, a4]，我们希望通过合并这些堆来最小化合并得分。
第一轮（i = 1）:
- 只考虑长度为 1 的子序列（即单个堆），
f[j][j + 1]表示单堆石子合并的代价为 0，因为每次合并需要至少两堆，所以f[j][j + 1] = 0。
- 只考虑长度为 1 的子序列（即单个堆），
第二轮（i = 2）：
- 考虑长度为 2 的子序列
[j, j + 1]，即选择两个相邻的堆进行合并。 - 对于每个子序列
[j, j + 2]，通过内层循环选择一个合并点k，比如可以选择k = j或k = j + 1，计算出最小合并得分。
- 考虑长度为 2 的子序列
第三轮（i = 3）：
- 考虑长度为 3 的子序列。我们会继续选择合适的分割点，计算最小得分。
以此类推，直到 i = n，表示合并整个序列。
#include <bits/stdc++.h>
using namespace std;
int n, a[501], f[501][501], s[501]; // n: 石子堆的数量，a: 每堆石子的数量，f: 动态规划表，s: 前缀和数组
int main()
{
cin >> n; // 读取石子堆的数量
for (int i = 1; i <= n; i++) // 输入每堆石子的数量
{
cin >> a[i]; // 读取第 i 堆的石子数量
a[n + i] = a[i]; // 为了模拟环形数组，重复一遍前 n 堆石子
}
n *= 2; // 扩展数组大小为 2n，处理环形问题
// 计算前缀和数组 s[], s[i] 表示前 i 堆石子的总数
for (int i = 1; i <= n; i++)
{
s[i] = s[i - 1] + a[i]; // 前缀和，s[i] = s[i-1] + a[i]，表示前 i 堆石子的总数
}
memset(f, 127, sizeof(f)); // 初始化动态规划表 f，设置为较大的数，表示最小值未计算
// 动态规划计算最小合并得分
for (int i = 1; i <= n; i++) // 遍历子序列的长度 i
{
for (int j = 1; j <= n - i; j++) // 遍历子序列的起始位置 j
{
for (int k = j; k < j + i; k++) // 遍历分割点 k
{
// 计算从 j 到 j+i 的子序列合并的最小得分
f[j][j + i] = min(f[j][j + i], f[j][k] + f[k + 1][j + i] + s[j + i] - s[j - 1]);
// f[j][j+i] 是从堆 j 到堆 j+i 的最小合并得分
// f[j][k] 和 f[k+1][j+i] 是子问题的解，s[j+i] - s[j-1] 是当前合并的代价
}
}
}
int ans = 1 << 30;
for (int i = 1; i <= n / 2; i++) // 查找从 1 到 n/2 的最小合并得分
{
ans = min(ans, f[i][i + n / 2 - 1]); // 从 f[i][i + n/2 - 1] 中寻找最小得分
cout << ans << endl; // 输出最小的得分
}
return 0;
}
树形动态规划
统计人数
dfs写法
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node{
node *next;
int where;
} *first[100001], a[100001];
int n, l, f[100001];
inline void makelist(int x,int y){//连一条从x到y的边
a[++l].where = y;
a[l].next = first[x];
first[x] = &a[l];
}
inline void solve(int i){
f[i] = 1;//一开始就自己一个人
for (node *x = first[i]; x; x = x->next)//找所有的儿子
{
solve(x->where);
f[i] += f[x->where];//加上儿子子树的个数
}
}
int main()
{
scanf("%d", &n);
memset(first, 0, sizeof(first));
l = 0;
for (int i = 2; i <= n;i++){
int x;
scanf("%d", &x);
makelist(x, i);
}
solve(1);//解决以1号点为子树的情况
for (int i = 1; i <= n;i++)
printf("%d ", f[i]);
return 0;
}
bfs写法
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
node *next;
int where;
} *first[100001], a[100001];
int n, l, f[100001], c[100001];
inline void makelist(int x, int y)
{ // 连一条从x到y的边
a[++l].where = y;
a[l].next = first[x];
first[x] = &a[l];
}
int main()
{
scanf("%d", &n);
memset(first, 0, sizeof(first));
l = 0;
for (int i = 2; i <= n; i++)
{
int x;
scanf("%d", &x);
makelist(x, i);
}
c[1] = 1;//队列，找出bfs序
for (int k = 1, l = 1; l <= k; l++)
{
int m = c[l];//头元素
for (node *x = first[m]; x; x = x->next)//下属点
c[++k] = x->where;
}
for (int i = n; i; i--)//倒着算的，算到前面的时候后面都计算过了
{
int m = c[i];
f[m] = 1;
for (node *x = first[m]; x; x = x->next)
{
f[m] += f[x->where];
}
}
for (int i = 1; i <= n; i++)
printf("%d ", f[i]);
}
没有上司的舞会
#include <bits/stdc++.h>
#define ll long long
using namespace std;
struct node
{
node *next;
int where;
} *first[100001], a[100001];
int n, l ,c[100001],v[100001];
ll f[100001][2];
inline void makelist(int x, int y)
{ // 连一条从x到y的边
a[++l].where = y;
a[l].next = first[x];
first[x] = &a[l];
}
inline void solve(int i){
f[i][1] = v[i];
for (node *x = first[i]; x;x=x->next){
solve(x->where);
f[i][0] += max(f[x->where][0], f[x->where][1]);
f[i][1] += f[x->where][0];
}
}
int main()
{
scanf("%d", &n);
memset(first, 0, sizeof(first));
l = 0;
for (int i = 2; i <= n;i++){
int x;
scanf("%d", &x);
makelist(x, i);
}
for (int i = 1; i <= n;i++)
scanf("%d", &v[i]);
solve(1);
printf("%lld\n", max(f[1][0], f[1][1]));
}
背包
01背包
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int v[N],w[N];
int f[N][N];
int main()
{
int n,m;cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j>=v[i])f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}
看一下 f[i][j] 的计算公式： f [ i ] [ j ] = m a x ( A , B ) f[i][j] = max(A, B) f[i][j]=max(A,B)。
只用到了 f [ i − 1 ] [ j ] f [ i − 1 ] [ j − v i ] f[i - 1][j]f[i-1][j - v_i] f[i−1][j]f[i−1][j−vi] ，即只用到了 f [ i − 1 ] f[i - 1] f[i−1] 这一层，并且用到的体积为 j j j 和 j − v i j - v_i j−vi，都是小于等于 j 的。
因此可以从体积为 V 开始，利用 f [ i − 1 ] f[i - 1] f[i−1]的数据，求解出 f [ i ] [ j ] f[i][j] f[i][j]，把 f [ i ] [ j ] f[i][j] f[i][j]放到 f [ i − 1 ] [ j ] f[i -1][j] f[i−1][j] 的位置上。这样 f 数组就能优化到一维了。并且，当 背包容量小于 v j v_j vj 的时候， f [ i ] [ j ] f[i][j] f[i][j] = max{ f [ i − 1 ] [ j ] f[i - 1][j] f[i−1][j]，0 } = f [ i − 1 ] [ j ] f[i - 1][j] f[i−1][j]。所以 j 只需要从 V 遍历到 v j v_j vj 即可。
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=1e3+10;
int v[N],w[N];
int f[N];
int main()
{
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=m;j>=v[i];j--)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout<<f[m];
return 0;
}
完全背包
#include<iostream>
using namespace std;
const int N = 1010;
int f[N][N];
int v[N],w[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1 ; i <= n ;i ++)
{
cin>>v[i]>>w[i];
}
for(int i = 1 ; i<=n ;i++)
for(int j = 0 ; j<=m ;j++)
{
for(int k = 0 ; k*v[i]<=j ; k++)
f[i][j] = max(f[i][j],f[i-1][j-k*v[i]]+k*w[i]);
}
cout<<f[n][m]<<endl;
return 0;
}
有了上面的关系，那么其实 k 循环可以不要了，核心代码优化成这样：
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int v[N],w[N];
int f[N][N];
int main()
{
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>v[i]>>w[i];
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
if(j-v[i]>=0)
f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);
}
}
cout<<f[n][m];
return 0;
}
f[i][j] = max(f[i][j],f[i-1][j-v[i]]+w[i]);//01背包
f[i][j] = max(f[i][j],f[i][j-v[i]]+w[i]);//完全背包问题
//0 1 背包代码优化这里有详细说明
#include<iostream>
using namespace std;
const int N = 1010;
int f[N];
int v[N],w[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1 ; i <= n ;i ++)
{
cin>>v[i]>>w[i];
}
for(int i = 1 ; i<=n ;i++)
for(int j = v[i] ; j<=m ;j++)
{
f[j] = max(f[j],f[j-v[i]]+w[i]);//注意了，这里的j是从小到大枚举，和01背包不一样
}
cout<<f[m]<<endl;
}
多重背包
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int f[N][N];
int n, m;
int main(){
cin >> n >> m;
for(int i = 1; i <= n; i ++) cin >> v[i] >> w[i] >> s[i];
for(int i = 1; i <= n; i ++){//枚举背包
for(int j = 1; j <= m; j ++){//枚举体积
for(int k = 0; k <= s[i]; k ++){
if(j >= k * v[i]){
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
}
cout << f[n][m] << endl;
return 0;
}
分组背包
#include <bits/stdc++.h>
using namespace std;
const int N=110;
int n,m,k;
int s[N],v[N][N],w[N][N];
int f[N][N];
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)
{
cin>>s[i];
for(int k=0;k<s[i];k++)
{
cin>>v[i][k]>>w[i][k];
}
}
for(int i=1;i<=n;i++)
{
for(int j=0;j<=m;j++)
{
f[i][j]=f[i-1][j];
for(int k=0;k<s[i];k++)
{
if(j>=v[i][k])
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[n][m]<<endl;
return 0;
}
因为只用到了第i-1列，所以可以仿照01背包的套路逆向枚举体积
#include<bits/stdc++.h>
using namespace std;
const int N=110;
int f[N];
int v[N][N],w[N][N],s[N];
int n,m,k;
int main(){
cin>>n>>m;
for(int i=0;i<n;i++){
cin>>s[i];
for(int j=0;j<s[i];j++){
cin>>v[i][j]>>w[i][j];
}
}
for(int i=0;i<n;i++){
for(int j=m;j>=0;j--){
for(int k=0;k<s[i];k++){ //for(int k=s[i];k>=1;k--)也可以
if(j>=v[i][k]) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
}
}
}
cout<<f[m]<<endl;
}