【C/C++】01背包问题/动态规划

按小蓝书上写的大数据情况下没过，按解答区一个大佬的修改了过了

#include <bits/stdc++.h>

using namespace std;

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

        // 创建dp数组

        vector <vector<int>> dp;

        vector <int> tmp;

        tmp.insert(tmp.begin(), V + 1, 0);

        for (int i = 0; i <= n; i++)

        {

            dp.push_back(tmp);

        }

        for (int i = 1; i <= n; i++)

        {

            for(int j = 1; j <= V; j++)

            {

                if (j < vw[i-1][0])

                {

                    dp[i][j] = dp[i-1][j];

                }

                else

                {

                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-vw[i-1][0]] + vw[i-1][1]);

                }

            }

            // for (int j = vw[i-1][0]; j <= V; j++)

            // {

            //     dp[i][j] = max(dp[i-1][j], dp[i-1][j-vw[i-1][0]] + vw[i-1][1]);

            // }

        }

        int maxx = 0;

        for (int i = 1; i <= V; i++)

        {

            maxx = max(dp[n][i], maxx);

        }  

        return maxx;

    }

}; 

int main()

{

    vector<vector<int>> arr {{1,3},{10,4}};

    int v = 10, n = 2;

    Solution solution;

    cout << solution.knapsack(v, n, arr) << endl;

    system("pause");

}

巴特西

【C/C++】01背包问题/动态规划

最新文章

热门文章