01背包求方案数问题
i :从零(或一)开始的前 i 个物品
j :当前可用背包容量
a[i] :从零(或一)开始的前 i 个物品的空间大小
dp[i,j] : 在前 i 个物品和值为j背包容量的情况下的方案数
算法一 :
二维数组 + 动态规划
状态转移方程:
- 不装前 i 个物品: 继承前一项 , 伪代码 :
dp[i, j] = dp[i - 1, j]
- 装前 i 个物品: 装从零(或一)开始的前 i 个物品 , 伪代码 :
dp[i, j] = dp[i - 1, j - A[i]]
所以总方案数 装前 i 个物品和不装前 i 个物品
注意:需初始化
dp[0,0] = 1
, 不然都是零
代码如下
#include <iostream>
using namespace std;
const int N = 10005;
int n, m;
int dp[N][N], a[N];
int main()
{
cin >> n >> m;
dp[0][0] = 1;
for (int i = 1; i <= n; i ++ )cin >> a[i];
for (int i = 1; i <= n; i ++ )
for (int j = 0; j <= m; j ++ )
{
dp[i][j] = dp[i - 1][j];
if (j >= a[i])
dp[i][j] += dp[i - 1][j - a[i]];
}
cout << dp[n][m];
}
要是数据在大一点, 估计会MLE+TLE
算法二 :
一维数组 + 动态规划 + 输入优化 + AC Saber
#include <iostream>
using namespace std;
const int N = 10005;
int n, m;
int dp[N];
int main()
{
cin >> n >> m;
dp[0] = 1;
for (int i = 0; i < n; i ++ )
{
int a;
cin >> a;
for (int j = m; j >= a; j -- )
dp[j] += dp[j - a];
}
cout << dp[m];
}