装箱问题（01背包）

约定不等于承诺〃 2022-08-07 09:59 120阅读 0赞

## 2599: 装箱问题 ##

**时间限制: **1 Sec

**内存限制: **128 MB

**提交: **84

**解决: **36

[提交][Link 1] [状态][Link 2]

### 题目描述 ###

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

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

### 输入 ###

第1行：一个整数，表示箱子容量。

第2行：一个整数，表示有n个物品

第3到n+2行，分别表示这n个物品的各自体积。

### 输出 ###

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

### 样例输入 ###

2468312797

### 样例输出 ###

0

提示

#include<cstdio>
    #include<iostream>
    using namespace std;
    #define max(a,b)a>b?a:b
    int main()
    {
        int v,n,i,j,a[20000],dp[30][10000]={0};
        cin>>v>>n;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
        }
        for(i=1;i<=n;i++)
        {
            for(j=0;j<=v;j++)
            {
                if(a[i]<=j)
                {
                    dp[i][j]=max(dp[i-1][j],dp[i-1][j-a[i]]+a[i]);
                }
                else
                {
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        printf("%d\n",v-dp[n][v]);
    }

[Link 1]: http://arena.acmclub.com/submitpage.php?id=2599
[Link 2]: http://arena.acmclub.com/problemstatus.php?id=2599

发表评论取消回复

表情：

评论列表（有 0 条评论，120人围观）

还没有评论，来说两句吧...

相关阅读

相关 01背包问题

[0-1背包问题][0-1] Reference: https://www.jianshu.com/p/a66d5ce49df5 问题描述： 0-1背包问题：给定

﹏ヽ暗。殇╰゛Y/ 2022年10月11日 13:40/ 0 赞/ 187 阅读

相关 01背包问题

1.题目有N件物品和一个容量为V的背包。第i件物品的成本是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大，要求是：物品只能放一次。 2.分

系统管理员/ 2022年09月10日 11:27/ 0 赞/ 153 阅读

相关装箱问题（01背包）

2599: 装箱问题时间限制: 1 Sec 内存限制: 128 MB 提交: 84 解决: 36 [提交][Link 1] [状态][Link 2] 题目描

约定不等于承诺〃/ 2022年08月07日 09:59/ 0 赞/ 121 阅读

相关 01背包问题

![Center][] ![Center 1][] [Center]: /images/20220616/e1a67e5ed0214bac8ec5293bc2b54

╰+攻爆jí腚メ/ 2022年06月16日 14:46/ 0 赞/ 166 阅读

相关 01背包问题

【例9.11】01背包问题时间限制: 1000 ms 内存限制: 65536 KB 【题目描述】一个旅行者有一个最多能装M公斤的背包，现在有n件物

淩亂°似流年/ 2022年06月08日 03:59/ 0 赞/ 163 阅读

相关背包问题—01背包、完全背包

01背包问题题目有m件物品和一个容量为V 的背包。放入第i 件物品占用的体积是Vi，得到的价值是Wi。求解将哪些物品装入背包可使价值总和最大。思路这

末蓝、/ 2022年05月30日 10:10/ 0 赞/ 273 阅读

相关洛谷P1049 装箱问题(01背包小变形)

题目描述有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30，每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱

青旅半醒/ 2022年05月28日 10:28/ 0 赞/ 108 阅读

相关 01背包问题

简单背包问题设有一个背包可以放入的物品重量为S，现有n件物品，重量分别是w1，w2，w3，…wn。问能否从这n件物品中选择若干件放入背包中，使得放入的重量之和正好为S

痛定思痛。/ 2022年05月26日 12:18/ 0 赞/ 163 阅读

相关洛谷 P1047 装箱问题——————01背包

题目描述有一个箱子容量为 VVV （正整数， 0≤V≤200000 \\le V \\le 200000≤V≤20000 ），同时有 nnn 个物品（ 0<n≤300<

港控/mmm°/ 2022年05月16日 10:21/ 0 赞/ 98 阅读

相关背包问题01

题目有N件物品和一个容量为V的背包。第i件物品的费用是c\[i\]，价值是w\[i\]。求解将哪些物品装入背包可使价值总和最大。基本思路这是最基础的背包问题，特

左手的ㄟ右手/ 2022年01月29日 11:34/ 0 赞/ 258 阅读