五、经典算法

1、动态规划

动态规划就是，给定一个问题，把它拆成一个个子问题，直到子问题可以直接解决。然后呢，把子问题答案保存起来，以减少重复计算。再根据子问题答案反推，得出原问题解的一种方法。

(1)背包问题

01背包问题

物品只有一个

课程链接 ： https://www.acwing.com/problem/content/2/
自己的笔记 ：https://www.acwing.com/activity/content/code/content/6168223/

赛前练习：01背包问题

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int N=1010;

int n,m;
int f[N];
int v[N],w[N];

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=m;j>=v[i];j--)//枚举所有体积
        {
            f[j]=max(f[j],f[j-v[i]]+w[i]);
        }
    }
    cout<<f[m];
    return 0;
}

重点：
1、状态表示；
2、状态更新；

完全背包问题