宣传一下算法提高课整理 <—

本题链接（AcWing）

https://www.acwing.com/problem/content/1026/

题目描述

有一个箱子容量为 V，同时有 n 个物品，每个物品有一个体积（正整数）。

要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入格式

第一行是一个整数 V，表示箱子容量。

第二行是一个整数 n，表示物品数。

接下来 n 行，每行一个正整数（不超过10000），分别表示这 n 个物品的各自体积。

输出格式

一个整数，表示箱子剩余空间。

数据范围

$0<V≤20000,$
$0<n≤30$

样例输入

24
6
8
3
12
7
9
7

样例输出

0

思路

这题其实就是01背包问题，只不过需要注意物品的体积和价值都是输入的$v[i]$数组

DP：

01背包大家再熟悉不过，就不多赘述了
注意阅读下列代码中的注释

$AC$ $Code$:

$C++$

#include <iostream>

using namespace std;

const int N = 20010; // 数组开到2e4足够

int V, n; // 总体积和物品个数
int v[N]; // 每个物品的体积
int f[N]; // 结果

int main()
{
    scanf("%d%d", &V, &n); // 输入背包体积V和物品数量n
    for (int i = 1; i <= n; i ++ )
        scanf("%d", &v[i]); // 读入n个物品的体积

    for (int i = 1; i <= n; i ++ )
        for (int j = V; j >= v[i]; j -- ) // 01背包的一维优化
            f[j] = max(f[j], f[j - v[i]] + v[i]); // 状态转移方程，注意体积和价值都是v[i]

    printf("%d\n", V - f[V]); // 输出，注意本题需要输出剩余体积，即V - f[V]

    return 0;
}

最后，如果觉得对您有帮助的话，点个赞再走吧！