算法提高课汇总

算法思路

理解题意

$01$背包问题:

1. 限制: 数值<-->体积; 且要求等于$M$, 即恰好.

2. 目的: 数量, 数值恰好为容量$M$的方案数

$DP$分析

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

• 集合: 从前$i$个数中选, 且总和恰好为$j$的所有方案

• 属性: Count, 方案数

状态计算

$01$背包问题, 以是否方案是否包含$a_i$作为划分依据:

• 不包含$a_i$, 问题等价于从前$i - 1$个数中选, 且总和恰好为$j$的所有方案, 根据定义其集合
  的方案数为$dp(i - 1, j)$.

• 包含$a_i$, 确定部分: $a_i$作为总和一部分; 剩余部分: 从前$i - 1$个数中选且总数恰好为$j - a_i$,
  对应集合的方案数为$dp(i - 1, j - a_i)$.

状态属性为Count: $dp(i, j) = dp(i - 1, j) + dp(i - 1, j - a_i)$.

代码实现

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

具体代码:

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;

int n, m;
int a[N];
int dp[M];

int main()
{
    cin >> n >> m;
    for( int i = 1; i <= n; i ++ )  cin >> a[i];

    dp[0] = 1; //dp(0, 0) = 1
    for( int i = 1; i <= n; i ++ )
        for( int j = m; j >= a[i]; j -- )
            dp[j] += dp[j - a[i]];
    cout << dp[m] << endl;

    return 0;
}