背包DP 01背包问题

状态表示f[i, j]:

集合：所有从前i个石头中，并且总体力/总体积不超过j的选法

属性：Max

状态计算：f[i, j] = max(f[i - 1, j], f[i - 1,j - c] + v)

思路：把精卫的体力看作容积，石头的体积看作价值，找到精卫在限定体力内能搬运的最大石头体积，如果f[C]大于需要的体积V，则说明可以填海，否则不能填海。

然后再从小到大遍历体力，找到最小的体力i使搬运的体积f[i] >= 需要的体积V

第二个变量j是体力的写法

#include <iostream>
using namespace std;

const int N = 10010;
int n, V, C;
int f[N];

int main()
{
    cin >> V >> n >> C;

    for (int i = 0; i < n; i++)
    {
        int v, c;
        cin >> v >> c;
        for (int j = C; j >= c; j--)
        {
            f[j] = max(f[j], f[j - c] + v);
        }
    }

    if (f[C] >= V)
    {
        for (int i = 0; i <= C; i++)
            if (f[i] >= V)
            {
                cout << C - i << endl;
                break;
            }
    }
    else puts("Impossible");
    return 0;
}

第二个变量j是总体积的写法

需要注意，因为求的是最小体积，所以一开始要初始化为正无穷

并且，状态转移方程有所变化：if (j >= v)说明当前石头不能直接填满体积v,则f[j] = min(f[j], f[j - v] + c)

else f[j] = min(f[j], c),当当前石头的体积可以直接填满j时，把这块石头耗费的体力，与之前的体力总和对比，取最小值

#include <iostream>
#include <cstring>
using namespace std;

const int N = 10010;
int n, V, C;
int f[N];

int main()
{
    cin >> V >> n >> C;
    memset(f, 0x3f, sizeof f);
    f[0] = 0;

    for (int i = 0; i < n; i++)
    {
        int v, c;
        cin >> v >> c;
        for (int j = V; j >= 0; j--)
        {
            if (j >= v)
                f[j] = min(f[j], f[j - v] + c);
            else
                f[j] = min(f[j], c);
        }
    }

    if (f[V] <= C)
    {
        cout << C - f[V] << endl;
    }
    else puts("Impossible");
    return 0;
}