01背包

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

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 计算01背包问题的结果
 * @param V int整型 背包的体积
 * @param n int整型 物品的个数
 * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
 * @param vwRowLen int vw数组行数
 * @param vwColLen int* vw数组列数
 * @return int整型
 *
 * C语言声明定义全局变量请加上static，防止重复定义
 */
int knapsack(int V, int n, int** vw, int vwRowLen, int* vwColLen ) {
    int *dp = (int *)malloc(sizeof(int) * ( V + 1));
    for (int i = 0; i<= V; i++) {
        dp[i] = 0;
    }
    /*
    for (int i = 0; i< n; i++) {
        for (int j = V; j >= vw[i][0]; j--) {
            int tmp = dp[j - vw[i][0]] + vw[i][1];
            if (tmp > dp[j])
                dp[j] = tmp;       
        }   
    }*/
    
    
    
    
    
    
    
    
    
    for (int i = 0 ;i < n; i++) {
        for (int j = V; j >= vw[i][0]; j--) {
            int temp = dp[j - vw[i][0]] + vw[i][1];
            if (temp > dp[j]) 
                dp[j] = temp;
        }
    }
    
    return dp[V];
}

C++ 解法, 执行用时: 4ms, 内存消耗: 468KB, 提交时间: 2022-05-28

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int v, int n, vector<vector<int> >& vw) {
        // write code here
        vector<int> dp(v + 1, 0);
        for(int i = 0; i < vw.size(); i++) {
            for(int j = v; j >= vw[i][0]; j--) {
                dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
            }
        }
        return dp[v];
        
    }
};

C 解法, 执行用时: 4ms, 内存消耗: 504KB, 提交时间: 2021-08-23

/**
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 计算01背包问题的结果
 * @param V int整型 背包的体积
 * @param n int整型 物品的个数
 * @param vw int整型二维数组 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
 * @param vwRowLen int vw数组行数
 * @param vwColLen int* vw数组列数
 * @return int整型
 */
int knapsack(int V, int n, int** vw, int vwRowLen, int* vwColLen ) {
    // write code here
    int* dp;
    int i = 0, j = 0;
    
    dp = (int*)malloc((V + 1) * sizeof(int));
    for(i = 0; i < V + 1; i++)
    {
        dp[i] = 0;
    }
//     memset((char*)dp, 0, (V + 1) * sizeof(int));
    for(i = 0; i < n; i++)
    {
        for(j = V; j >= vw[i][0]; j--)
        {
            if(j >= vw[i][0])
            {
                if(dp[j - vw[i][0]] + vw[i][1] > dp[j])
                    dp[j] = dp[j - vw[i][0]] + vw[i][1];
            }
        }
    }
    
    return dp[V];
}

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

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        vector<int> dp(V + 1, 0);
        for(int i = 0; i < n; ++i){
            for(int j = V; j >= vw[i][0]; j--)
                dp[j] = max(dp[j], dp[j - vw[i][0]] + vw[i][1]);
        }
        return *max_element(dp.begin(), dp.end());
    }
};

C++ 解法, 执行用时: 4ms, 内存消耗: 512KB, 提交时间: 2021-04-02

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算01背包问题的结果
     * @param V int整型 背包的体积
     * @param n int整型 物品的个数
     * @param vw int整型vector<vector<>> 第一维度为n,第二维度为2的二维数组,vw[i][0],vw[i][1]分别描述i+1个物品的vi,wi
     * @return int整型
     */
    int knapsack(int V, int n, vector<vector<int> >& vw) {
        // write code here
        vector<int> dp(V+1,0);
        for(int i =1;i<=n;i++)
        {
            for(int j=V;j>0;j-- )
            {
                if(j>=vw[i-1][0])
                {
                    dp[j]=max(dp[j],dp[j-vw[i-1][0]]+vw[i-1][1]);
                }
            }
        }
        return dp[V];
    }
};

详情