【题目链接】
ybt 1295:装箱问题
ybt 1917:【01NOIP普及组】装箱问题
OpenJudge NOI 2.6 8785:装箱问题
洛谷 P1049 [NOIP2001 普及组] 装箱问题
【题目考点】
1. 动态规划:01背包问题
【解题思路】
该题不能用贪心解决。
如果贪心选择为:每次选择能放入的最大体积的物品。设箱子大小为4,三个物品大小为3 2 2。那么按照贪心选择,会选择3,剩余空间1。但选择两个2是最优解,剩余空间0。如果贪心选择为:每次选择最小体积的物品。设箱子大小为3,两个物品大小为3 2。按照贪心选择,会选择2,剩余空间1。实际选择3是最优解。
该题需要用动规方法解决。
1. 状态定义
集合:物品选择的方案限制:物品选择的范围,箱子大小属性:剩余空间条件:最小统计量:剩余空间状态定义:dp[i][j]
:在前i个物品中选择物品放入大小为j的箱子的各种方案中剩余空间最小的方案的剩余空间。
初始状态:
将i个物品放入大小为0的箱子,剩余空间只能为0。所以dp[i][0] = 0
。将0个物品放入大小为j的箱子,剩余空间只能为j。所以dp[0][j] = j
。
2. 状态转移方程
记第i个物品的体积为a[i]
。
集合:在前i个物品中选择物品放入大小为j的箱子的各种方案。
依据第i物品是否放入箱子来分割集合。
子集1:不把第i物品放入箱子。那么只能在前i-1个物品中选择物品放入大小为j的箱子。在前i个物品中选择物品放入大小为j的箱子的最小剩余空间即为:在前i-1个物品中选择物品放入大小为j的箱子的最小剩余空间。即dp[i][j] = dp[i-1][j]
。子集2:在可以将第i物品放入箱子的前提下,确定把第i物品放入箱子,那么箱子剩余空间为j-a[i]。接下来要在前i-1个物品中选择物品放入大小为j-a[i]的箱子。此时在前i个物品中选择物品放入大小为j的箱子的最小剩余空间为:在前i-1个物品中选择物品放入大小为j-a[i]的箱子的最小剩余空间,即dp[i][j] = dp[i-1][j-a[i]]
。以上两种情况取最小值。
可以对该题使用滚动数组优化,使用一维数组作为状态。
【题解代码】
解法1:基本解法 二维状态
#include<bits/stdc++.h>using namespace std;#define N 35#define V 20005int 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;}
解法2:滚动数组优化 一维状态
#include<bits/stdc++.h>using namespace std;#define N 35#define V 20005int dp[V], a[N];//dp[i][j]:在前i个物品中选择物品放入大小为j的箱子的方案中剩余空间最小的方案的剩余空间int main(){int v, n;cin >> v >> n;for(int i = 1; i <= n; ++i)cin >> a[i];//a[i]:第i物品的体积 for(int j = 1; j <= v; ++j)//设初值,前0个物品放入大小为j的箱子,剩余空间为j dp[j] = j;for(int i = 1; i <= n; ++i)for(int j = v; j >= a[i]; --j)dp[j] = min(dp[j], dp[j-a[i]]);cout << dp[v];return 0;}
信息学奥赛一本通 1295:装箱问题 | 1917:【01NOIP普及组】装箱问题 | OpenJudge NOI 2.6 8785 | 洛谷 P1049 [NOIP2001 普及组] 装箱问题