做网站郴州,全屏网站设计,重庆建筑工程信息管理平台,超级门户wordpress企业主题1917#xff1a;【01NOIP普及组】装箱问题 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4178 通过数: 2473
【题目描述】 有一个箱子容量为VV(正整数#xff0c;0≤V≤200000≤V≤20000#xff09;#xff0c;同时有n个物品#xff08;0≤n≤300≤n≤30),…1917【01NOIP普及组】装箱问题 时间限制: 1000 ms 内存限制: 65536 KB 提交数: 4178 通过数: 2473
【题目描述】 有一个箱子容量为VV(正整数0≤V≤200000≤V≤20000同时有n个物品0≤n≤300≤n≤30),每个物品有一个体积正整数。要求从nn个物品中任取若干个装入箱内使箱子的剩余空间为最小。 【输入】 第一行是箱子的容量,第二行是nn(表示nn有nn个物品),接下来nn行是nn个物品的体积。 【输出】 最小空间 【输入样例】
24
6
8
3
12
7
9
7
【输出样例】
0 思路
很明显这是一道动态规划题
我们看别人的代码可以知道这里要用二维数组
所以
dp[i][j]表示在前i个物品中选择物品放入大小为j的箱子的方案中剩余空间最小的方案的剩余空间
我们来举个例子来计算dp【3】【5】
我们要如何将物品放入箱子呢
我们有两种方案
1、放入a【3】物品此时dp【3】【5】dp【2】【5- a[3] 】
因为我们放入了物品剩余的空间相当于将前2件放入空间为5-a【3】的箱子中因为放了东西所以要 -a【3】很合理
2、不放入a【3】物品此时dp【3】【5】 dp【2】【5】
因为我们没有放入物品剩余的空间相当于将前2件放入空间为5的箱子中因为没放东西所以不用 -a【3】很合理
还有些特殊情况
还是计算dp【3】【5】a【3】5这时候我们就不能将a【3】放进箱子了只能选择2号方案 这是很久以前开始写的题解今天看到了就写完吧
这个代码肯定是从哪里借鉴抄来的但我忘记抄的哪里的 代码
//抄的
#includebits/stdc.h
using namespace std;
#define N 35//让N永远等于35
#define V 20005
int v, n, dp[N][V], a[N];//dp[i][j]在前i个物品中选择物品放入大小为j的箱子的方案中剩余空间最小的方案的剩余空间
int main()
{cin v n;for(int i 1; i n; i)cin a[i];//a[i]第i物品的体积 for(int j 0; j v; j)//设初值前0个物品放入大小为j的箱子剩余空间为j dp[0][j] j;for(int i 1; i n; i)for(int j 0; j v; j){if(j a[i])dp[i][j] min(dp[i-1][j], dp[i-1][j-a[i]]);elsedp[i][j] dp[i-1][j];}cout dp[n][v];return 0;
}
