摘要
Title: 4700. 何以包邮？
Tag: dp、背包、装箱问题
Memory Limit: 64 MB
Time Limit: 1000 ms

4700. 何以包邮？

题意

新学期伊始，适逢顿顿书城有购书满 x 元包邮的活动，小 P 同学欣然前往准备买些参考书。
一番浏览后，小 P 初步筛选出 n 本书加入购物车中，其中第 i 本（1≤i≤n）的价格为 ai 元。
考虑到预算有限，在最终付款前小 P 决定再从购物车中删去几本书（也可以不删），使得剩余图书的价格总和 m 在满足包邮条件（m≥x）的前提下最小。
试帮助小 P 计算，最终选购哪些书可以在凑够 x 元包邮的前提下花费最小？
思路

装箱问题
- dfs（非正解）
  n最大为30，如果要枚举全部情况的话，大约 $2^{30} = 1073741824$ ，是 $1e10$ 的数量级，显然过不了，但我想，如果剪枝可能能过，但可惜也过不了
  当然双向DFS是可以过的，但我没学，过几天一定补上！！！
- 装箱问题（正解）
  从题目数据中，我们可以得知价钱最多为 $30 * 1e4 = 3e5$ $30 * 1 e 4 = 3 e 5$ ，所以就有了下面的递推式，总共大约 $9e6$ $9 e 6$ 的复杂度
  - f[i]表示是否存在花费总和为i的方案，1代表存在，0代表不存在
  - 初始状态，f[0] = 1，代表存在总和为0的方案，就是什么都不选
  - 从价格最大值3e5从大到小枚举，状态方程为 $f[j] |= f[j - w[i]]$
  - 最后，遍历f数组，从x开始到最大值，第一个为TRUE的下标就是答案
  - 附图
- 01背包（dp）（正解）
  将此题进行模型转换，也可以对应到背包问题（x代表包邮条件 sum代表书的总价值）
  我们现在要实现
  - 在选了sum之后，去掉几本书，使得总价格在大于等于x的条件下，越小越好 ——对象是买的书
  - 等价于
  - 选择若干本书去掉，在去掉的这几本书，使得总和不超过 $sum-x$ 的前提下，总和越大越好 ——对象是去掉的书
    所以，我们就可以对应到01背包问题了
  - 背包容量： $sum-x$
  - 每个物品体积： $w[i]$
  - 每个物品价值： $w[i]$
  - 最后求出来的是尽量填满的书的花费，用sum减去，即是答案
    也就是01背包问题也可以转化为，n个物品，体积为v[i]，价值为w[i]，在装满V的条件下，价值最小

代码

dfs

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-13 17:59:07
* @FilePath: \Acwing\4700\4700.cpp
* @LastEditTime: 2023-01-13 18:27:47
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 35, INF = 0x3f3f3f3f;

int n, x;
int w[N];
int ans = INF;

void dfs(int u, int sum)
{
    if (ans == x || (ans > x && sum > ans)) // 如果有大于x的答案了，但此时sum还大于答案，就直接return
        return;

    if (sum >= x)
        ans = min(ans, sum);

    for (int i = u; i <= n; ++i)
        dfs(i + 1, sum + w[i]);
}

signed main()
{
    IOS;
    cin >> n >> x;
    for (int i = 1; i <= n; ++i)
        cin >> w[i];

    sort(w + 1, w + 1 + n);

    dfs(1, 0);
    cout << ans;
    return 0;
}

装箱问题

/*
* @Author: NEFU AB-IN
* @Date: 2023-01-13 18:28:44
* @FilePath: \Acwing\4700.1\4700.1.cpp
* @LastEditTime: 2023-01-13 18:46:23
*/
#include <bits/stdc++.h>
using namespace std;
#define int long long
#undef int

#define SZ(X) ((int)(X).size())
#define ALL(X) (X).begin(), (X).end()
#define IOS                                                                                                            \
    ios::sync_with_stdio(false);                                                                                       \
    cin.tie(nullptr);                                                                                                  \
    cout.tie(nullptr)
#define DEBUG(X) cout << #X << ": " << X << '\n'
typedef pair<int, int> PII;

const int N = 35, M = 3e5 + 10, INF = 0x3f3f3f3f;

int n, x;
int w[N];
bool f[M];

signed main()
{
    IOS;
    cin >> n >> x;
    for (int i = 0; i < n; ++i)
        cin >> w[i];

    f[0] = 1;
    for (int i = 0; i < n; ++i)
    {
        for (int j = M; j >= w[i]; --j)
        {
            f[j] |= f[j - w[i]];
        }
    }
    for (int i = x; i <= M; ++i)
    {
        if (f[i])
        {
            cout << i;
            return 0;
        }
    }
    return 0;
}

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

using namespace std;

const int N = 33, M = 300010;

int n, x;
int w[N], f[M];

int main()
{
    scanf("%d%d", &n, &x);

    int sum = 0;
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &w[i]);
        sum += w[i];
    }

    int m = sum - x;
    for (int i = 0; i < n; i ++ )
        for (int j = m; j >= w[i]; j -- )
            f[j] = max(f[j], f[j - w[i]] + w[i]);

    printf("%d\n", sum - f[m]);
    return 0;
}

4700. 何以包邮？

题意

思路

代码