有一个箱子容量为 V,同时有 n 个物品,每个物品有一个体积(正整数)。

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

输入格式

  • 第一行是一个整数 V,表示箱子容量。
  • 第二行是一个整数 n,表示物品数。
  • 接下来 n 行,每行一个正整数(不超过10000),分别表示这 n 个物品的各自体积。

输出格式

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

数据范围

0 < V ≤ 20000, 0 < n ≤ 30

输入样例

24
6
8
3
12
7
9
7

输出样例

0

题目分析

01背包

代码实现

#include <iostream>
using namespace std;
const int N = 2e4 + 10;

int n, V, v, dp[N];
int main () {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> V >> n;
    while(n--) {
        cin >> v;
        for (int i = V; i >= v; --i) dp[i] = max(dp[i], dp[i - v] + v);
    }
    cout << V - dp[V];
    return 0;
} 
分类: DP

0 条评论

发表回复

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注

友情链接:Ctips' blog, Colza’s blog

站点状态:Status