【算法|动态规划 | 01背包问题No.1】AcWing 426. 开心的金明

原题链接：点击直接跳转到该题目

1️⃣题目描述

2️⃣题目解析

状态表示：dp[i][j]表示从前i个物品中进行挑选且总价钱不超过j的情况下，价格与重要度的乘积的总和的最大值。

状态转移方程：

• 选择第i件物品：dp[i][j] = dp[i - 1][j]
• 不选择第i件物品（前提是j >= V[i]）：dp[i][j] = dp[i - 1][j - V[i]] + V[i] * W[i]

注意可以使用滚动数组进行空间优化，填表时需要从右往左进行填表。

3️⃣解题代码

朴素算法：

#include<iostream>
using namespace std;

const int M = 26;
const int N = 30000;
int dp[M][N],V[M],W[M];

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> V[i] >> W[i];
    for(int i = 1;i <= m;i++)
    {
        for(int j = 1;j <= n;j++)
        {
            dp[i][j] = dp[i - 1][j];
            if(j - V[i] >= 0) dp[i][j] = max(dp[i][j],dp[i - 1][j - V[i]] + V[i] * W[i]);
        }
    }
    cout << dp[m][n] << endl;
}

滚动数组进行空间优化代码：

#include<iostream>
using namespace std;

const int M = 26;
const int N = 30000;
int dp[N],V[M],W[M];

int main()
{
    int n,m;
    cin >> n >> m;
    for(int i = 1;i <= n;i++) cin >> V[i] >> W[i];
    for(int i = 1;i <= m;i++)
    {
        for(int j = n;j >= V[i];j--)
        {
            dp[j] = max(dp[j],dp[j - V[i]] + V[i] * W[i]);
        }
    }
    cout << dp[n] << endl;
}