【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背包问题/动态规划

原文：https://www.cnblogs.com/kinologic/p/14672453.html