C++ 解法, 执行用时: 4ms, 内存消耗: 416KB, 提交时间: 2022-04-26

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param V int整型 
     * @param num int整型vector 
     * @return int整型
     */
    int boxin(int V, vector<int>& num) {
        // write code here
        vector<int> dp(V + 1, 0);
        dp[0] = 0;
        for (int i = 0; i < num.size(); i++) {
            for (int j = V; j >= 1; j--) {
                if (num[i] <= j) {
                    dp[j] = max(dp[j], dp[j - num[i]] + num[i]);
                }
            }
        }
        return V - dp[V];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 420KB, 提交时间: 2022-08-06

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param V int整型 
     * @param num int整型vector 
     * @return int整型
     */
    int boxin(int V, vector<int>& num) {
        // write code here
        vector<int> dp(V+1,0);
        dp[0]=0;
        for(int i=0;i<num.size();i++)
        {
            for(int j=V;j>=1;j--)
            {
                if(num[i]<=j)
                {
                    dp[j]=max(dp[j],dp[j-num[i]]+num[i]);
                }
            }
        }
        return V-dp[V];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 436KB, 提交时间: 2022-07-30

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param V int整型
     * @param num int整型vector
     * @return int整型
     */
    int boxin(int v, vector<int>& nums) {
        int n=nums.size();
        /*
        vector<vector<int>> dp(n+1,vector<int>(v+1,0));
        dp[0][0]=0;
        */
        vector<int> dp(v+1,0);
        dp[0]=0;
         
        for(int i=1;i<=n;++i){
            int cur=nums[i-1];
            for(int j=v;j>=0;--j){
                if(j-cur>=0){
                    //dp[i][j]=max(dp[i-1][j],dp[i-1][j-cur]+cur);
                    dp[j]=max(dp[j],dp[j-cur]+cur);
                }
                /*
                else{
                    //dp[i][j]=dp[i-1][j];
                    dp[j]=dp[j];//可省略
                }
                */
            }
        }
         
        return v-dp[v];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 444KB, 提交时间: 2022-07-30

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param V int整型 
     * @param num int整型vector 
     * @return int整型
     */
    int boxin(int v, vector<int>& nums) {
        int n=nums.size();
        vector<int> dp(v+1);
        
        for(int i=0;i<n;++i){
            int cur=nums[i];
            for(int j=v;j>=cur;--j){
                dp[j]=max(dp[j],dp[j-cur]+cur);
            }
        }
        
        return v-dp[v];
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 444KB, 提交时间: 2022-06-15

bool dp[20005];
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param V int整型 
     * @param num int整型vector 
     * @return int整型
     */
    int boxin(int V, vector<int>& num) {
        // write code here
        // 本质上是背包问题
        memset(dp,0,sizeof dp);
        dp[0] = true;
        int n = num.size();
        for(int i = 0;i < n;i++){
            for(int j = V;j >= num[i];j--)
                dp[j] = dp[j] || dp[j - num[i]];
        }
//         for(int j =  V;j >= 0;j--){
//             for(int x : num){
//                 if (j >= x) dp[j] = dp[j] || dp[j-x];
//             }
//         }
        int j = V;
        while(!dp[j]) j--;
        return V - j;
        
    }
};