算法提高课汇总

算法思路

理解题意

背包问题 :

1. 限制
   • 容量V
   • 重量M
2. 目的: 价值Max

Y氏DP分析:

相比于$01$背包问题, 这里需要额外表示一个限制: 可以用状态的一个额外维度表示.

状态表示 $dp(i, j, k)$

• 集合: 从前$i$个物品中选择, 且总体积不超过$j$、总重量不超过$k$的所有选法

• 属性: Max物品价值

状态计算

01背包: 以物品$i$选或不选作为划分集合依据.

• 不选物品$i$: 问题等价于从前$i-1$个物品中选择, 且限制条件不变: 对应的集合最大值为$dp(i-1,j,k)$.

• 选择物品$i$: 确定部分: 选择物品$i$, 带来了$w_i$的收益, 且对限制条件造成影响: 需要为物品$i$预留
  $v_i$的体积和$m_i$的重量. 剩余可变部分等价于:
  $\;\;\;\;$从前$i$个物品中选择, 且总体积不超过$j-v_i$、总重量不超过$k-m_i$的所有选法,
  对应集合最大值为: $dp(i-1,j-v_i,k-m_i)$.

为保持状态$dp(i,j,k)$的Max属性, 从其两个子集取最大值: $dp(i,j,k) = max\lbrace dp(i-1,j,k), dp(i-1,j-v_i,k-m_i) + w_i\rbrace$.

相比于$01$背包问题: 在问题分析上多考虑一个条件; 在具体实现上多一维限制.

代码实现

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110;

int n, V, M;
int dp[N][N];

int main()
{
    cin >> n >> V >> M;

    for( int i = 1; i <= n; i ++ )
    {
        int v, m, w;
        cin >> v >> m >> w;
        for( int j = V; j >= v; j -- )
            for( int k = M; k >= m; k -- )
                dp[j][k] = max( dp[j][k], dp[j - v][k - m] + w );
    }
    cout << dp[V][M] << endl;

    return 0;
}