顺丰小哥派件装载问题——典型的01背包问题

题目：比赛的时候没看这一题- -！！没想到竟然是一个典型的01背包问题，早知道这样我早写这题就好了，我真的栓Q了。

思路：与背包问题对比：

背包问题：假设有容量为15kg的背包，有多个容量不同的物品，需要放入背包，如何装物品使得在背包容量范围内获得尽量大的重量。

装载问题：快递箱容量为V，有n个体积大小不同的快递，需要放入快递箱，如何装快递使得在快递箱不溢出的情况下，剩余空间最小。

所以，发现，两者问题没有丝毫差别，还等什么？直接肝啊！

动规五部曲：

*1* dp数组含义：dp[i]表示当装入 体积 为 i 的快递后，快递箱中快递能得到的最大容量；

*2* 递推公式：两种情况，装还是不装，选择其中最大值：dp[i]=max(dp[i],dp[i-N[j]]+N[j]);

*3* 初始化：dp[0]=0;

*4* 遍历顺序；

*5* 打印dp

注意：dp写法一般有两种，分为二维dp和一维滚动dp，不同写法，要注意 背包和物品 的遍历顺序，以及背包的装法，是从后往前装还是从前往后装。

动规写法有点遗忘，第一次写的时候背包和物品的遍历次序忘了，后面自己复习了一下

代码：

 

class Solution {
public:
    
    int dpfun(vector<int>&N,int V)
    {
        vector<int>dp(V+1,0);//能装入体积为i的背包的最大容量
        //初始化 dp[0]=0;
        //递推公式 dp[i]=max(dp[i],dp[i-N[j]]+N[j]);
        //循环顺序：从前往后
        //递推公式
            for(int j=0;j<N.size();j++)//遍历物品
            {
                 for(int i=V;i>=N[j];i--)//遍历背包
                {
                    dp[i]=max(dp[i],dp[i-N[j]]+N[j]);
                }
            }
       return dp[V];
    }
    int minRemainingSpace(vector<int>& N, int V) {
        sort(N.begin(),N.end());
        if(N[0]>V)return V;
        for(auto &it:N)
        {
            if(it==V)
                return 0;
        }
        int result=V-dpfun(N,V);
        
        return result;
    }
};