P1049 装箱问题

题目描述

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

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

输入输出格式

输入格式:

一个整数,表示箱子容量

一个整数,表示有n个物品

接下来n行,分别表示这n 个物品的各自体积

输出格式:

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

输入输出样例

输入样例#1:

24
6
8
3
12
7
9
7

输出样例#1:

0

说明

NOIp2001普及组 第4题

比较裸的01背包问题,

他让着求最小剩余量

那我们只要求出最大能装多少就好

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 using namespace std;
 6 int maxt,n;
 7 int dp[31][20001];
 8 int v[31];
 9 int read(int & n)
10 {
11     char p='+';int x=0;
12     while(p<'0'||p>'9')
13         p=getchar();
14     while(p>='0'&&p<='9')
15     x=x*10+p-48,p=getchar();
16     n=x;
17 }
18 int main()
19 {
20     read(maxt);read(n);
21     for(int i=1;i<=n;i++)
22         read(v[i]);
23     for(int i=1;i<=n;i++)
24         for(int j=0;j<=maxt;j++)
25             if(j>=v[i])
26                 dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]);
27             else
28                 dp[i][j]=dp[i-1][j];
29     cout<<maxt-dp[n][maxt];
30     return 0;
31 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏Albert陈凯

scala的option和some

对于学习 Scala 的 Java™ 开发人员来说,对象是一个比较自然、简单的入口点。在 本系列 前几期文章中,我介绍了 Scala 中一些面向对象的编程方法,...

29550
来自专栏学习力

《Java从入门到放弃》JavaSE入门篇:运算符

18160
来自专栏玄魂工作室

如何学python 第十七课 类-面向对象的概念

欢迎回来。今天要说的东西将会改变我们写程序的方式。今天我们介绍‘类’(class)。 概述 什么叫‘类’?类,类型。变量类型。从日常生活的感觉来说,‘类’其实...

28140
来自专栏技术专栏

合唱团

题目:有 n 个学生站成一排,每个学生有一个能力值,从这 n 个学生中按照顺序选取 k 名学生,要求相邻两个学生的位置编号的差不超过 d,使得这 k 个学生的能...

10620
来自专栏趣谈编程

选择排序

面试官: 聊聊选择排序 选择排序是一种简单直观的算法,今天我们聊聊选择排序的思想,代码以及复杂度 排序思想 一天,小一尘和师傅下山去了,在集市中路经一个水果摊,...

34380
来自专栏magicsoar

Effective Modern C++翻译(6)-条款5:auto比显示的类型声明要更好

    在概念上说,auto关键字和它看起来一样简单,但是事实上,它要更微妙一些的。使用auto会让你在声明变量时省略掉类型,同时也会防止了手动类型声明带来的正...

215100
来自专栏软件开发 -- 分享 互助 成长

简单工厂模式

一、简单工厂模式的相关概念: 1、定义:简单工厂模式是属于创建型模式,又叫做静态工厂方法(Static Factory Method)模式。 其核心思想就是有一...

19290
来自专栏老九学堂

零基础学Java第三讲变量

如何掌握了变量这个语法?看看微视频中对应的知识点的讲解。 别走开,下面有干货哦! 1了解什么是变量?变量如何使用? 2会使用常用的数据类型 任何编程语言的语...

31750
来自专栏C语言C++游戏编程

C语言讨论象棋将帅问题,代码短又美!

问题的本身并不复杂,只要把所有A、B 互相排斥的条件列举出来就可以完成本题的要 求。由于本题要求只能使用一个变量,所以必须首先想清楚在写代码的时候,有哪些信息需...

14530
来自专栏C语言C++游戏编程

因为有你,所以出彩!C语言编程中不可或缺的条件判断和循环

在编程语言中,判断和循环可以说是最重要的之一,正因为实现了它们的功能,才能够有如今各种各样功能的程序。今天小编带大家来了解一些条件判断和循环的知识。

15030

扫码关注云+社区

领取腾讯云代金券