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

正文索引 [隐藏]

题目描述:

有一个箱子容量为V(正整数,0<=V<=20000),同时有n个物品(0<n<=30),每个物品有一个体积(正整数)。
要求n个物品中,任取若干个装入箱内,使箱子的剩余空间为最小。

输入描述:

第一行为一个整数,表示箱子容量;第二行为一个整数,表示有n个物品。接下来n行,每行一个整数表示这n个物品的各自体积。

输出描述:

一个整数,表示箱子剩余空间。

输入样例:

24
6
8
3
12
7
9
7

输出样例:

解题思路:

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;
}