【蓝桥杯】ALGO-21 装箱问题
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
本文链接：https://blog.csdn.net/weixin_42449444/article/details/102985133
题目描述：
有一个箱子容量为V（正整数，0＜=V＜=20000），同时有n个物品（0＜n＜=30），每个物品有一个体积（正整数）。 要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。
输入描述：
第一行为一个整数，表示箱子容量；第二行为一个整数，表示有n个物品。接下来n行，每行一个整数表示这n个物品的各自体积。
输出描述：
一个整数，表示箱子剩余空间。
输入样例：
24
6
8
3
12
7
9
7 输出样例：
0解题思路：
01背包问题。要使剩余空间最小，则需要让物品占用背包的体积最大。dp[i][j]表示前i件物品放入体积为j的背包后所占用的最大体积。将物品放入背包时需要考虑俩种情况：①若要放入的物品体积大于背包容量则不考虑放入背包；②若要放入的物品体积小于背包容量则考虑放入背包或者不放入背包，取占用体积较大的那种情况。dp[n][v]就是将n件物品放入体积为v的背包后所占用的最大体积，用v-dp[n][v]就是最后的输出结果。
AC代码：
#include <bits/stdc++.h>
using namespace std;
#define Up(i,a,b) for(int i = a; i <= b; i++)
const int maxv = 20001;
const int maxn = 31;
int dp[maxn][maxv]; //dp[i][j]表示前i件物品放入体积为j的背包后的最大体积
int main()
{
ios::sync_with_stdio(false);
cin.tie(0),cout.tie(0);
int v,n; //箱子容量v,物品数n
cin >> v >> n;
Up(i,1,n)
{
int _;
cin >> _;
Up(j,1,v)
{
if(_ > j) //当前物品体积大于背包容量就不放入背包
{
dp[i][j] = dp[i-1][j];
}
else //当前物品体积小于背包容量,考虑放入还是不放入背包
{
dp[i][j] = max(dp[i-1][j],dp[i-1][j-_]+_);
}
}
}
cout << v-dp[n][v] << endl;
return 0;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2019-11-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录