【动态规划】01背包专题

01背包在恰好等于的情况下求最小物品数

MELON的难题

每个物品（石头）的价值w[i]就是其自己的个数，为1
体积题目已给出。

状态定义：f[i][j]表示在前i个物品中选，且体积总和恰好等于j需要的物品个数的最小值

初始化：
f[i][0] = 0 , 1 <= i <= n
f[0][j] = INF, 1 <= j <= m，答案是f[n][m]

二维版本

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

using namespace std;

const int N = 32 * 1000 / 2 + 10, INF = 0x3f3f3f3f;

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i], sum += v[i];

    if (sum % 2) puts("-1");
    else
    {
        m = sum / 2;
        // 本题初始化是重中之重，卡了两天了
        // 起点1是因为从1开始读入的,终点m是容量，不能写成n物品件数
        for (int j = 1; j <= m; j++) f[0][j] = INF;
        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] = min(f[i][j], f[i - 1][j - v[i]] + 1);
            }
        }
        if (f[n][m] == INF) cout << "-1";
        else cout << f[n][m];
    }
    return 0;
}

一维版本

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

using namespace std;

const int N = 32 * 1000 / 2 + 10, INF = 0x3f3f3f3f;

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

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> v[i], sum += v[i];

    if (sum % 2) puts("-1");
    else
    {
        m = sum / 2;
        // 本题初始化是重中之重，卡了两天了
        // 起点1是因为从1开始读入的,终点m是容量，不能写成n物品件数
        for (int j = 1; j <= m; j++) f[j] = INF;
        for (int i = 1; i <= n; i++)
        {
            for (int j = m; j >= v[i]; j--)
            {
                f[j] = min(f[j], f[j - v[i]] + 1);
            }
        }
        if (f[m] == INF) cout << "-1";
        else cout << f[m];
    }
    return 0;
}