01背包的模板

朴素的二维（便于理解，也不会卡内存。二维稳过，一维优化看思路和时间）

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 1100;
int f[N][N];
int w[N],v[N];
int n,m;
int main()
{
    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]<<endl;
    return 0;
}

利用滚动数组一维优化，注意背包容量的遍历顺序（从大到小）

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1010;
int f[N];
int w[N],v[N];
int n,m;
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
    f[0]=0;
    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]<<endl;
    return 0;
}

完全背包的模板

朴素的三维版本（肯定超时，纯暴力，最朴实的思路，便于之后的优化）

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1100;
int f[N][N];
int w[N],v[N];
int n,m;
int main()
{
    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++)
            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;
}

完全背包优化后的二维,二重循环

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1100;
int f[N][N];
int w[N],v[N];
int n,m;
int main()
{
    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][j-v[i]]+w[i]); 
        }
    cout<<f[n][m]<<endl;
    return 0;
}

利用滚动数组一维优化

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int  N= 1010;
int f[N];
int v[N],w[N];
int n,m;
int main()
{
    cin>>n>>m;
    for (int i=1;i<=n;i++) cin>>v[i]>>w[i];
    f[0]=0;
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++)
            if (j>=v[i]) f[j]=max(f[j],f[j-v[i]]+w[i]);
    cout<<f[m]<<endl;
    return 0;
}

背包问题的实际应用（将会每天持续更新）

完全背包求解方案数问题

鸣人的影分身

 #include <iostream>
#include <cstdio>
using namespace std;
const int N = 11;
int main()
{
    int T;
    scanf("%d",&T);
    while (T--)
    {
        int n,m;
        scanf("%d%d",&n,&m);
        int f[N][N]={0};
        f[0][0]=1;  //当总和为0，且个数为0的情况只有1种，就是{0}
        for (int i=0;i<=n;i++)  //注意，i要从0开始，因为可能存在总和为0的情况
            for (int j=1;j<=m;j++) //分成的个数至少为1
                {
                    f[i][j]=f[i][j-1];  //当分的情况中有0的时候，就等价与在总和为i，个数为j-1的分类方法
                    if (i>=j) f[i][j]+=f[i-j][j];  //每个数都减去1，总和变成了i-1*j，个数依旧是j个
                }
        printf("%d\n",f[n][m]);
    }
    return 0;
}

最长回文子序列问题应用

密码脱落

#include <iostream>
#include <string>
using namespace std;
const int N = 1010;
int f[N][N];  //表示区间[l,r]的回文序列的集合，集合的属性也就是我们要求的是所有回文序列的长度的最大值
int main()
{
    string s;
    cin>>s;
    int len=s.size();  //获取字符串长度
    for (int i=1;i<=len;i++)  //先枚举区间的长度
    {
        for (int l=0;l+i-1<len;l++)  //枚举左端点，左端点的取值范围为0~l+区间长度-1
        {
            int r=l+i-1;
            if (i==1) f[l][r]=1;  //当区间长度为1，即序列只有一个字母时，必定是回文子序列，此序列的长度为1
            else
            {
                if (s[l]==s[r]) f[l][r]=f[l+1][r-1]+2;  //左右端点都考虑在内，而且此时左端点必定等于右端点
                if (f[l+1][r]>f[l][r]) f[l][r]=f[l+1][r];  //此时只考虑右端点，不考虑左端点
                if (f[l][r-1]>f[l][r]) f[l][r]=f[l][r-1]; //此时只考虑左端点，不考虑右端点
            }
        }
    }
    int ans=len-f[0][len-1];  //答案等于字符串长度减去最长回文子序列长度
    cout<<ans<<endl;
    return 0;
}

01背包问题求最大价值问题

糖果

 #include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 110;
int f[N][N];
int n,k;
int main()
{
    cin>>n>>k;
    memset(f,-0x3f,sizeof f);  //初始化为服务穷鬼
    f[0][0]=0;  //从0件物品中选且总和%k==0的方案中，最大的个数为0
    for (int i=1;i<=n;i++)
    {
        int w;
        cin>>w;
        for (int j=0;j<k;j++)  //%k的取值范围为0~k-1
        {
            f[i][j]=max(f[i-1][j],f[i-1][((j-w)%k+k)%k]+w); 
        }
    }
    cout<<f[n][0];  //最终的答案是从n件物品中选取，且%k==0的方案中总数最大的那个
    return 0;
}

路径迷宫问题dp

摘花生

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 110;
int f[N][N];
int w[N][N];
int T;
int main()
{
    cin>>T;
    while (T--)
    {
        int n,m;
        cin>>n>>m;
        for (int i=1;i<=n;i++)
            for (int j=1;j<=m;j++)
                cin>>w[i][j];
        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])+w[i][j];
        cout<<f[n][m]<<endl;
    }
    return 0;
}

最长上升子序列的模板

最长上升子序列

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int N = 1010;
int f[N];  //定义为以i为右端点的上升子序列长度的最大值
int a[N]; 
int n;
int main()
{
   cin>>n;
   for (int i=1;i<=n;i++) cin>>a[i];
   for (int i=1;i<=n;i++)
   {
       f[i]=1;  //每个位置的初始值为1，因为本身自己一个数构成长度为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<<endl;
   return 0;
}