蓝桥杯算法提高VIP-01背包

01背包问题是动态规划领域中的经典问题，其主要问题可以概括为：给定n个物品和一个背包，物品i的重量为v[i]，价值为w[i]，背包的最大承载重量为m。问如何选取物品装入背包，以使得背包中物品的总价值最大，同时不超过背包的最大承载重量。每个物品只能被选择次或1次。

上述代码给出了01背包问题的解决方案。下面是该问题的详细题解：

1. **定义状态**：首先定义一个二维数组f[N][M]，其中f[i][j]表示只考虑前i个物品，当前背包容量为j时可以获得的最大价值。N和M分别代表物品数量和背包容量的上限，这里它们被设定为205和5005，以满足一般情况。

2. **状态转移方程**：对于每个物品i，我们有两种选择：不放入背包或放入背包。如果不放入背包，则当前状态f[i][j]即为不考虑物品i时的状态，也就是f[i-1][j]；如果选择放入背包，则f[i][j]应为f[i-1][j-v[i]] + w[i]，即考虑减去物品i重量后的上一个状态加上物品i的价值。综合这两种选择，可以得到状态转移方程：f[i][j] = max(f[i-1][j], f[i-1][j-v[i]] + w[i])。

3. **初始化**：这里隐性地初始化了状态数组f[][]，在C++中，静态数组默认初始化为，这符合01背包问题的初始化条件，即当没有物品或背包容量为时，可获得的最大价值为。

4. **遍历顺序**：首先遍历物品i (1 <= i <= n)，然后遍历背包容量j (1 <= j <= m)。这样可以保证在计算f[i][j]时，所有需要的状态已经被计算过。

5. **输出结果**：最终，f[n][m]就表示考虑所有物品，当背包容量为m时可以获得的最大价值，直接输出即可。

#include <bits/stdc++.h>
using namespace std;
 
const int N=205;
const int M=5005;
 
int n,m;
int v[N],w[N];
int f[N][M];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    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++)
        {
            if(j<v[i])f[i][j]=f[i-1][j];
            else f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }
    }
    cout<<f[n][m];
    return 0;
}