博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
P1049 装箱问题
阅读量:5127 次
发布时间:2019-06-13

本文共 764 字,大约阅读时间需要 2 分钟。

P1049 装箱问题

题目描述

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

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

输入输出格式

输入格式:

 

一个整数,表示箱子容量

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

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

 

输出格式:

 

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

 

输入输出样例

输入样例#1:
2468312797
输出样例#1:
0

说明

NOIp2001普及组 第4题

 

分析:

跟采药相比也就少了个每个物品的价值,但物品的体积也可以看作是它的价值,最后总体积减去最大体积就是答案

01背包的模板题。f[j]=max{f[j],d[j-v]+v}(j>=v)表示盒子体积为j时装入最大体积。注意输出时要C-[C]

 

1 #include
2 #include
3 using namespace std; 4 //d[i]表示前i个物品,最大体积 5 const int maxn=20001; 6 7 int main() 8 { 9 int C,n,V,f[maxn]={
0};10 scanf("%d%d",&C,&n);11 for(int i=0;i
=V;j--)15 f[j]=max(f[j],f[j-V]+V);16 }17 printf("%d",C-f[C]);18 return 0;19 }

 

 

 

 

转载于:https://www.cnblogs.com/Renyi-Fan/p/7424909.html

你可能感兴趣的文章
HTTP之报文
查看>>
Perl正则表达式匹配
查看>>
windows下的文件管理工具--total commander
查看>>
四元数
查看>>
功率谱密度如何理解
查看>>
git clean解决 GIT error: The following untracked working tree files would be overwritten
查看>>
windows下的计算时间间隔 -- GetTickCount()
查看>>
Excel在数据表中悬停鼠标显示数据值
查看>>
UML类图知识
查看>>
香农的伟大论文《A Symbolic Analysis of Relay and Switching Circuits》
查看>>
OpenMark
查看>>
c++11 enum class用法
查看>>
excel中怎么将行转换为列及列转换成行
查看>>
git 版本(commit) 回退
查看>>
c++ 数值计算库Eigen
查看>>
CodeMeter 软件加密技术
查看>>
git 版本库之间的依赖
查看>>
python全栈开发中级班全程笔记(第三模块、第一章(多态、封装、反射、内置方法、元类、作业))...
查看>>
react-01
查看>>
sublime插件安装
查看>>