关键词：
装箱问题
题目描述 Description
有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述 Input Description
一个整数v，表示箱子容量
一个整数n，表示有n个物品
接下来n个整数，分别表示这n 个物品的各自体积
一个整数，表示箱子剩余空间。
样例输入 Sample Input
24
6
8
3
12
7
9
7
0
其实就是一个一维的dp。每输入一个物体a[i]就更新体积为j（a[i]≤j≤V）的背包的最大体积值即可。
1 #include <iostream> 2 #include <cmath> 3 #include <cstring> 4 #include <cstdio> 5 #include <cstdlib> 6 #include <algorithm> 7 using namespace std; 8 int a[35]; 9 int f[20101]; 10 int main() 11 { 12 int n,V; 13 scanf("%d%d",&V,&n); 14 for(int i=1;i<=n;i++) 15 { 16 scanf("%d",&a[i]); 17 for(int j=V;j>=a[i];j--) f[j]=max(f[j],f[j-a[i]]+a[i]); 18 } 19 printf("%d",V-f[V]); 20 //system("pause"); 21 return 0; 22 }
codevs1014装箱问题（dp）
题目大意：http://codevs.cn/problem/1014/源码：#include<iostream>#include<cmath>#include<cstdio>#include<algorithm>#include<cstring>usingnamespacestd;intv,n;intarr[50];intmain(){c 查看详情
1014装箱问题code[vs]
1014装箱问题 2001年NOIP全国联赛普及组 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解 查看运行结果 题目描述 Description有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝... 查看详情
codevs1014装箱问题
题目描述 Description有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入描述 InputDescripti... 查看详情
noip装箱问题(代码片段)
题目：[NOIP2001]装箱问题，哈哈，我们今天来看一道很古老的题嘛，这是选自NOIP上的一道题，好了，我们一起来看看题意吧：考虑到直接复制题目，或者截屏的方式不是很方便阅读，我就把直接... 查看详情
codevs1038一元三次方程求解noip2001提高组
题目链接：http://codevs.cn/problem/1038/题解： 嗯，exm？才知道二分隶属搜索专题…… 对-100到100枚举，按照题目中的提示，当当fi*fi+1<0时，二分深搜，直到精度达到小数点后4位为止（保守起见），当fi*fi+1=0时，判定... 查看详情
codevs1013求先序排列2001年noip全国联赛普及组x
题目描述Description给出一棵二叉树的中序与后序排列。求出它的先序排列。（约定树结点用不同的大写字母表示，长度<=8）。输入描述InputDescription两个字符串，分别是中序... 查看详情
[noip2001]普及组
装箱问题裸01背包，速刷过1#include<cstdio>2#include<iostream>3#include<cmath>4usingnamespacestd;5intsp[50000]={0};6intf[50000]={0};7intmain(){8intv,n;9cin>>v>>n;10inti,j;11for( 查看详情
noip装箱问题(代码片段)
题目：[NOIP2001]装箱问题，哈哈，我们今天来看一道很古老的题嘛，这是选自NOIP上的一道题，好了，我们一起来看看题意吧：考虑到直接复制题目，或者截屏的方式不是很方便阅读，我就把直接... 查看详情
dp学习之装箱问题
CodeVS1014有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。INPUT:VN每个物品的体积OUTPUT:箱子剩余空... 查看详情
codevs3152装箱问题3
装箱问题3http://codevs.cn/problem/3152/题目描述 Description设有n种物品，记作A1、A2、…、An，对应于每个Ai（1<=i<=n）都有一个重量Awi和价值Avi（重量和价值都为正整数）。另外，对应于每个Ai，都有一件可代替它的“代用品”Bi... 查看详情
codevs1464装箱问题2x
题目描述Description一个工厂制造的产品形状都是长方体，它们的高度都是h，长和宽都相等，一共有六个型号，他们的长宽分别为1*1,2*2,3*3,4*4,5*5,6*6。这些产品通常使用一个6*6*h的... 查看详情
关于noip的问题
...法原理**2001-c3二叉树的先序序列递归或穷举，构造**2001-c4装箱问题宽搜+hash表，或动态规划***2001-g1一元三次方程求解穷举或随机化+迭代**200 查看详情
2001装箱问题
题目描述 Description有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）。要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。输入描述 InputDescripti... 查看详情
18.2.13codevs1012最大公约数和最小公倍数问题
1012最大公约数和最小公倍数问题2001年NOIP全国联赛普及组 题目描述 Description输入二个正整数x0,y0(2<=x0<100000,2<=y0<=1000000),求出满足下列条件的P,Q的个数条件: 1.P,Q是正整数2.要求P,Q以x0为最大公约数,以y0为最小公... 查看详情
codevs1145hanoi双塔问题2007年noip全国联赛普及组
时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题目描述 Description给定A、B、C三根足够长的细柱，在A柱上放有2n个中间有孔的圆盘，共有n个不同的尺寸，每个尺寸都有两个相同的圆盘，注意这两个圆盘是不加区分的（... 查看详情
codevs3289noip2013花匠
http://codevs.cn/problem/3289/dp转移，树状数组维护前缀max和后缀max进行优化，$O(nlogn)$。#include<cstdio>#include<cstring>#include<algorithm>usingnamespacestd;constintN=100003;intin(){ intk=0,fh=1;charc= 查看详情
codevs——1039数的划分
1039数的划分 2001年NOIP全国联赛提高组 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold题解 题目描述 Description将整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。例如：n=7... 查看详情
[codevs]1014棋盘染色
1049棋盘染色 时间限制:1s 空间限制:128000KB 题目等级:黄金Gold 题目描述 Description有一个5×5的棋盘，上面有一些格子被染成了黑色，其他的格子都是白色，你的任务的对棋盘一些格子进行染色，使得所有的黑... 查看详情