JHwong

用户名：dotcpp0724243

访问量：832

签　名：

等　　级
排　　名	3383
经　　验	1946
参赛次数	11
文章发表	16
年　　龄	0
在职情况	学生
学　　校	宁波大学科学技术学院
专　　业

　　自我简介：

TA的其他文章

1435: 蓝桥杯历届试题-国王的烦恼
浏览：156

1427: 蓝桥杯2013年第四届真题-买不到的数目
浏览：39

2529: NOIP2012-同余方程-了解即可
浏览：34

你可能喜欢

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

[NOIP2001]装箱问题 - 如何转换为经典题型

　　作者: JHwong　　　　发表时间：2024-01-10 21:52:02 浏览：31　|　评论：1　

原题链接：[NOIP2001]装箱问题

# [NOIP2001]装箱问题 - 如何转换为经典题型
## 解题思路：
### 思路1：搜索
这是最简单的思路，从某种角度来说。穷搜算法就是一种枚举状态的思路。因此这是无视防御的思维路径。因为在理论上，只要可以在规定时间内进行穷搜，就一定可以使用该思路。但这不是我们介绍的重点。因此，此题的穷搜代码我不会展示。总体上说，穷搜代码不是应该不是很难，使用DFS应该就可以。
### 思路2：完全背包问题
在提议描述中，我们关注到了几个点，如下成列：
- 取若干个
- 容积上界为volume of box
- 存在消耗代价 cost = volume of goods
- 最优化问题
因此，我们可以锁定是完全背包问题。因为抓取的关键词匹配完全背包的关键词描述。因此，我们在进一步下定义，因为题目获取的是剩余空间最小。这里就有两个等价条件，如下：
1. DP[]直接存放最下剩余价值, answer = dp[0];
2. DP[]存放最大可存放价值，answer = volume of box - dp[volume of box];
只要定义恰当的DP数组就可以开始编写了，我们给出了两个版本的DP数组的相应代码。

####DP数组定义1
```cpp
/*
 * 题目 1283: [NOIP2001]装箱问题
 * 是一个完全背包问题 - 记录代价是剩余的容积（Volume）
 * dp数组：>= m 最少的剩余容积。
 * answer = dp[0] ">=0容积的最少剩余容积"
 * 这里采取不等式是压缩了空间 -- 空间优化
 * 为什么是>=?
 * 只要符合逻辑就行，如果定义dp[m]=x<=m的最小剩余。这样答案就是dp[volume of box]。
 * 但是，我个人觉得不足的是初始化的时候在语义上x<=0的最少剩余容积是volume of box是违背常理的，so，我还是选择了比较符合语义说法的dp[m]=x>=m的最小容积
 */
#include<iostream>
#include<cstring>
#define MAX_NUMBER_OF_GOODS    35
#define MAX_VOLUME_OF_BOX   20010

const int volume_of_box = 0;
int number_of_goods;
int volume_of_goods[MAX_NUMBER_OF_GOODS];
int dp[MAX_VOLUME_OF_BOX];
int main() {
  scanf("%d", volume_of_goods + volume_of_box);
  scanf("%d", &number_of_goods);
  for (int i = 1; i <= number_of_goods; ++i) scanf("%d", volume_of_goods + i);

for (int i = 0; i <= volume_of_goods[volume_of_box]; ++i) dp[i] = volume_of_goods[volume_of_box];
  for (int cur_goods_index = 1; cur_goods_index <= number_of_goods; ++cur_goods_index)
  for (int cur_rest_volume = 0; cur_rest_volume <= volume_of_goods[volume_of_box] - volume_of_goods[cur_goods_index]; ++cur_rest_volume)
  {
  int cost = dp[cur_rest_volume + volume_of_goods[cur_goods_index]] - volume_of_goods[cur_goods_index];
    if (cost < 0) cost = volume_of_goods[volume_of_box];
    if (dp[cur_rest_volume] > cost) dp[cur_rest_volume] = cost;
  }
  printf("%d\n", dp[0]);
  return 0;
}
```

#### DP数组定义2
```cpp
/*
 * 题目 1283: [NOIP2001]装箱问题
 * 是一个完全背包问题 - 记录代价是剩余的容积（Volume）
 * 所以反着来求取m - dp[m]。 dp表示容积<=m的最大存放量
 * debug记录：
 * e...竟然错在打错变量名了...一定小心hhh。
 */
#include<iostream>
#include<cstring>
#define MAX_NUMBER_OF_GOODS    35
#define MAX_VOLUME_OF_BOX   20010

for (int cur_goods_index = 1; cur_goods_index <= number_of_goods; ++cur_goods_index)
    for (int cur_rest_volume = volume_of_goods[volume_of_box]; cur_rest_volume >= volume_of_goods[cur_goods_index]; --cur_rest_volume)
  {
    int cost = dp[cur_rest_volume - volume_of_goods[cur_goods_index]] + volume_of_goods[cur_goods_index];
    if (cost > volume_of_goods[volume_of_box]) cost = 0;
    if (dp[cur_rest_volume] < cost) dp[cur_rest_volume] = cost;
  }
  printf("%d\n", volume_of_goods[volume_of_box] - dp[volume_of_goods[volume_of_box]]);
  return 0;
}
```

0.0分

0 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

JHwong

这里编码优点小问题，可读性可能会差了点。应该定义宏定义
#define volume_of_box volume_of_goods[0]
这样可读性更好，也节省了4字节空间。

2024-01-11 00:20:52

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

【作业调度方案】（C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

[NOIP2001]装箱问题 - 如何转换为经典题型

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

众数问题（C语言代码）

三角形（C++代码）记忆化搜索

矩阵乘方（C语言代码）

字符串输入输出函数（C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

JHwong

TA的其他文章

你可能喜欢

C语言程序设计教程（第三版）课后习题1.6 （C++代码）

【作业调度方案】 （C语言代码）

C语言训练-阶乘和数* （C++代码）（直接输出样例hhhh）

C语言程序设计教程（第三版）课后习题6.9 （C++代码）论pow函数的应用

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

[NOIP2001]装箱问题 - 如何转换为经典题型

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题8.9 （C语言代码）

C语言训练-列出最简真分数序列* （C语言代码）

2003年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

众数问题 （C语言代码）

三角形 （C++代码）记忆化搜索

矩阵乘方 （C语言代码）

字符串输入输出函数 （C语言代码）

C语言程序设计教程（第三版）课后习题10.1 （C语言代码）

C语言程序设计教程（第三版）课后习题6.4 （C语言代码）

C语言程序设计教程（第三版）课后习题1.5 （C语言代码）

【作业调度方案】（C语言代码）

　　评论区

众数问题（C语言代码）

三角形（C++代码）记忆化搜索

矩阵乘方（C语言代码）

字符串输入输出函数（C语言代码）