算法提高课汇总

算法思路

理解题意

1. 限制
   • 书的价格<-->体积, 且要求全部买书, 即“恰好”
   • 每本书的数量任意
2. 目的
   • 数量, 买书的不同方案的数量

所以本题是一个完全背包求方案数的问题, 完全背包的分析可以参考🔗.

$DP$分析

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

• 集合: 从前$i$本书中选, 且所有价格恰好为$j$的所有方案

• 属性: Count, 方案数

状态计算

对于状态$dp(i,j), $第$i$个物品数量$k$可选范围: $k\in [0,\lfloor \frac{j}{v_i}\rfloor]$.

为不失一般性, 考虑第$i$个物品选择$k$个的状态, $k\in [0,\lfloor \frac{j}{v_i}\rfloor]$ :
问题转变为: 从前$i - 1$个物品中选择且总价格等于$j - k\times v_i$的所有选法.

• 固定部分: 第$i$个物品选择了$k$个, 其对应价格为$k\times v_i$.

• 可变部分: 根据定义, 其对应集合的数量为$dp(i - 1, j - k\times v_i)$

状态的属性为Count: $dp(i, j) = \sum_{k = 0}^{\lfloor \frac{j}{v_i}\rfloor}dp(i-1, j-k\times v_i)$

也就是$dp(i, j)$是$dp(i-1, j\%v_i \sim j)$的总和, 可以视为前缀和. 回忆我们计算前缀和时的公式:

$\;\;\;\;sum_i = sum_{i - 1} + a_i$.

$dp(i, j)$的计算公式可以优化为: $dp(i, j) = dp(i, j - v_i) + dp(i-1, j)$.

注意 : 状态$dp(i, j - v_i)$可能由于价格限制不存在, 视为$\varnothing$.

代码实现

• 初始化: $dp(0, 0) = 1, dp(0, i) = 0, i\gt 0$. 由定义出发, 从前$0$个数字只能构成$0$, 且方案数
  只有一种: 啥都不选.

空间朴素版本

#include <iostream>

using namespace std;

const int N = 1010;

int m;
int v[] = {0, 10, 20, 50, 100};
int dp[5][N];

int main()
{
    cin >> m;
    dp[0][0] = 1; 
    for( int i = 1; i <= 4; i ++ )
    {
        for( int j = 0; j <= m; j ++ )
        {
            dp[i][j] = dp[i - 1][j];
            if( j >= v[i] )
                dp[i][j] += dp[i][j - v[i]];
        }
    }
    cout << dp[4][m] << endl;

    return 0;
}

空间优化

代码的等价变形.

#include <iostream>

using namespace std;

const int N = 1010;

int m;
int v[] = {0, 10, 20, 50, 100};
int dp[N];

int main()
{
    cin >> m;
    dp[0] = 1; 
    for( int i = 1; i <= 4; i ++ )
        for( int j = v[i]; j <= m; j ++ )
                dp[j] += dp[j - v[i]];
    cout << dp[m] << endl;

    return 0;
}