【藍橋杯】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;  }