首页 日常,🐶算法

题目

0.png

思路

dp[i][j]表示前i个物品体积为j时的最大价值

那么最后的结果就是在dp[i][0~v]里面找最大的价值

状态转移方程:
1.不选i:不选i就是直接加体积即可
dp[i][j] = dp[i - 1][j]
2.选i:选择i即为当前体积减去i的体积的前i-1物品的最大价值加上i的价值(此处要注意当前体积减去i体积应大于等于0要不然装不下)
dp[i][j] = dp[i - 1][j - v[i]] + w[i]

dp[0][0] = 0

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m, res = 0;
    vector<vector<int>> dp = vector<vector<int>>(1010, vector<int>(1010, 0));
    vector<int> v = vector<int>(1010, 0);
    vector<int> w = vector<int>(1010, 0);
    cin>>n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin>>v[i] >>w[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= m; j++)
        {
            dp[i][j] = dp[i - 1][j];
            if (j >= v[i])
            {
                dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]);
            }
        }
    }
    for (int i = 0; i <= m; i++)
    {
        res = max(res, dp[n][i]);
    }
    cout<<res<<endl;
    return 0;
}

优化

前面用的是二维数组,题目最后求的是dp[i][0~v],i是不动的,所以可以把二维数组优化为一维数组。

dp[j]表示N件物品体积为j时的最优解。
因为之前的二维dp[i][j]的状态是由i - 1求来的,如果换成一维后还是从0遍历那么dp[j]的状态就不是由i - 1求来,而是由i求来。所以遍历背包容量的时候要从m开始从后往前遍历。

新的状态转移方程:dp[j] = max(dp[j], dp[j - v[i]] + w[i]);

#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    int n, m;
    vector<int> dp = vector<int>(1010, 0);
    vector<int> v = vector<int>(1010, 0);
    vector<int> w = vector<int>(1010, 0);
    cin>>n >> m;
    for (int i = 1; i <= n; i++)
    {
        cin>>v[i] >>w[i];
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = m; j >= v[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    cout<<dp[m]<<endl;
    return 0;
}



文章评论