---
title: "背包问题求方案数"
created: 2025-11-28
tags:
  - 算法
---

# 背包问题求方案数

## 题目 [背包问题求方案数](https://www.acwing.com/problem/content/11/)

![[image-47c1a00b.png]]

## 思路分析

做这道题之前先写一下 [数字组合](https://flowus.cn/8d388c90-f276-44b1-9c88-0954170f1c23)

数字组合这题问的是所有方案数 就是简单的把原来集合的max属性变成了count属性

而这道题要我们求的是 最大价值的方案数

实际上就是把原本的01背包（求最大价值）和这个变形的01背包（求方案数）做一个结合

在同一dp过程中 同时把这两件事做了即可

### 思路

- `f[i][j]`记录考虑前`i`件物品，当前背包容量为`j`时的最大价值。
- `g[i][j]`记录在考虑前`i`件物品，当前背包容量为`j`时，达到最大价值`f[i][j]`的方案数。

1. 初始化：`f[0][0]`不需要管 默认为0 从前0个物品中选体积不超过0的物品的总价值的最大值自然是0 `g[i][0] = 1`无论考虑多少物品
   总存在一种方案使得容量为0的背包达到价值0 即不选择任何物品
2. 动态规划更新：

- 遍历物品`i`从1到`n`，和背包容量`j`从`0`到`m`。
- 更新`f[i][j]`：如果不取当前物品，则价值为`f[i-1][j]`；如果取当前物品（前提是`j`大于等于物品体积`v[i]`），则价值为`f[i-1][j-v[i]] + w[i]`，取两者的较大值。
- 更新`g[i][j]`：
  - 如果`f[i][j]`的值来源于`f[i-1][j]`（即不取当前物品），则方案数为`g[i-1][j]`。
  - 如果`f[i][j]`的值来源于`f[i-1][j-v[i]] + w[i]`（即取当前物品），则方案数为`g[i-1][j-v[i]]`。
  - 注意，如果`f[i][j]`同时满足上述两种情况，即`f[i][j]`的值既可以通过不取当前物品也可以通过取当前物品得到，那么`g[i][j]`应该累加这两种情况的方案数。

1. 最后，遍历`j`从0到`m`，累加所有`f[n][j]`等于`f[n][m]`（即最大价值）时的`g[n][j]`值，得到的总和就是最终的方案数。

### **问题：**

为什么累加所有f[n][j]等于f[n][m]（即最大价值）时的g[n][j]值，得到的总和就是最终的方案数？  我们知道g[n][j]的含义是从前n个物品当中选
体积不超过j的所有达到最大价值的方案数 如果某个方案只选到了k(k是小于n的）就已经达到了最大价值f[n][m] 那它还需要表示为前n个物品中选吗
或者换句话说 所疑惑的这种情况 是否被包含进了g[n][0-m]当中？比如达到最大价值 此时只在k个物品中选了3 即g[k][3] 好像g[n][3]也包括了这个g[k][3]？

### **分析：**

#### 动态规划的状态定义和转移

在0-1背包问题中，状态f[i][j]表示考虑前i个物品，当前背包容量为j时的最大价值。状态g[i][j]记录的是达到这个最大价值的方案数。这里的重点是"考虑前`i`个物品"并不意味着必须选择第`i`个物品，也不意味着必须恰好选`i`个物品。它意味着在前`i`个物品中进行选择，不超过容量`j`的条件下可以达到的最大价值及其方案数。

#### 考虑不同数量的物品

当我们说g[n][j]包括了g[k][3]（对于某个`k < n`和某个容量`3`），实际上我们是在说：在计算g[n][j]时，我们考虑了所有从第1个物品到第`n`个物品的可能组合，其中包括了那些仅使用前`k`个物品达到某个价值的所有方案。

#### 如何理解“考虑前`n`个物品”中包含了更少物品的情况

动态规划的过程是累积的。当我们在计算f[i][j]和g[i][j]的值时，我们是基于之前所有的计算结果来的。这意味着，如果存在一个最优的方案，它实际上只选取了前`k`个物品中的一部分，那么这个方案在计算f[k][x]和g[k][x]时已经被考虑过，并且它的价值和方案数被递推到了f[n][j]和g[n][j]。

这是因为，当我们从`k`递推到`n`时，如果后面的物品没有被选择（即它们不增加总价值），`f`和`g`的值仍然会保留那个最大价值和对应的方案数，因为我们在动态规划中是通过比较和选择最大值来更新状态的。

### 结论

因此，即使某个最优方案实际上只选择了前`k`个物品中的一些，这个方案仍然会被包含在最终的`g[n][j]`中，因为在递推过程中，我们考虑了所有可能的物品组合，包括那些在中途就已经达到最大价值的方案。这就是动态规划的美妙之处：它通过局部最优解的累积，最终得到全局最优解，并能够统计达到这个全局最优解的所有可能的方案数。

### 代码

现在对于f[][]和g[][]的理解应该有一些了吧

那么再考虑最后一个问题

f[n][m]毋庸置疑是最大答案 我们01背包取最大价值就是取它

根据前面的分析 f[n][0-m]显然就是其他选法的总价值 它对应的选法数量都在g[n][0-m]当中

那么只要发现f[n][j]里有和我们最大价值f[n][m]相等的值 就把那些选法数量（g[n][j])累加起来

朴素：

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int v[N], w[N];
int f[N][N], g[N][N];
int n, m;

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

    // 初始化方案数为1，即不选任何物品的情况
    for (int i = 0; i <= n; i++)
        g[i][0] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i-1][j]; // 不选第i个物品
            g[i][j] = g[i-1][j]; // 继承不选的方案数

            if (j >= v[i]) {
                if (f[i][j] < f[i-1][j-v[i]] + w[i]) {
                    f[i][j] = f[i-1][j-v[i]] + w[i]; // 更新最大价值
                    g[i][j] = g[i-1][j-v[i]]; // 更新方案数
                } else if (f[i][j] == f[i-1][j-v[i]] + w[i]) {
                    g[i][j] = (g[i][j] + g[i-1][j-v[i]]) % mod; // 累加方案数
                }
            }
        }
    }

    int res = 0;
    for (int j = 0; j <= m; j++) {
        if (f[n][j] == f[n][m]){
            res = (res + g[n][j]) % mod;
        }
    }
    cout << res;

    return 0;
}
```

接着就是老套路 消掉一维

```cpp
#include<bits/stdc++.h>
using namespace std;

const int N = 1010, mod = 1e9 + 7;
int v[N], w[N];
int f[N], g[N];
int n, m;

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

    g[0] = 1;
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--) {
            if (f[j] < f[j-v[i]] + w[i]) {
                f[j] = f[j-v[i]] + w[i]; // 更新最大价值
                g[j] = g[j-v[i]]; // 更新方案数
            } else if (f[j] == f[j-v[i]] + w[i]) {
                g[j] = (g[j] + g[j-v[i]]) % mod; // 累加方案数
            }
        }
    }

    int res = 0;
    for (int j = 0; j <= m; j++) {
        if (f[j] == f[m]){
            res = (res + g[j]) % mod;
        }
    }
    cout << res;

    return 0;
}
```

我的这种理解方式是和y总以及其他题解不太一样的 但是和铅笔哥是差不多思路

感觉要比什么更改状态从不超过j变为恰好等于j要容易理解些

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010,mod=1e9+7;

int v[N],w[N];

int f[N][N],g[N][N];

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)

        cin>>v[i]>>w[i];

    for(int i=0;i<=n;i++)

        g[i][0]=1;

    for(int i=1;i<=n;i++){

        for(int j=0;j<=m;j++){

            f[i][j]=f[i-1][j];

            g[i][j]=g[i-1][j];

            if(v[i]<=j){

                if(f[i][j]<f[i-1][j-v[i]]+w[i]){

                    f[i][j]=f[i-1][j-v[i]]+w[i];

                    g[i][j]=g[i-1][j-v[i]];

                }

                else if(f[i][j]==f[i-1][j-v[i]]+w[i])

                    g[i][j]=(g[i][j]+g[i-1][j-v[i]])%mod;

            }

        }

    }

    int res=0;

    for(int j=0;j<=m;j++)

        if(f[n][j]==f[n][m])

            res=(res+g[n][j])%mod;

    cout<<res;

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=1010,mod=1e9+7;

int v[N],w[N];

int f[N],g[N];

int n,m;

int main()

{

    cin>>n>>m;

    for(int i=1;i<=n;i++)

        cin>>v[i]>>w[i];

    g[0]=1;

    for(int i=1;i<=n;i++){

        for(int j=m;j>=v[i];j--){

            if(f[j]<f[j-v[i]]+w[i]){

                f[j]=f[j-v[i]]+w[i];

                g[j]=g[j-v[i]];

            }

            else if(f[j]==f[j-v[i]]+w[i])

                g[j]=(g[j]+g[j-v[i]])%mod;

        }

    }

    int res=0;

    for(int j=0;j<=m;j++)

        if(f[j]==f[m])

            res=(res+g[j])%mod;

    cout<<res;

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[背包问题求具体方案数|背包问题求具体方案数]] 🏠 [[00-刷题理模型]] ➡️ [[跳台阶|跳台阶]]