【蓝桥杯】ALGO-21 装箱问题

• 2019 年 11 月 13 日
• 笔记

版权声明：本文为博主原创文章，遵循 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;  }