python

11 KiB

Raw Permalink Blame History Unescape Escape

This file contains invisible Unicode characters that may be processed differently from what appears below. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to reveal hidden characters.

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 11. 背包问题求方案数

一、题目描述

有 N 件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 v_i，价值是 w_i。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。

输出 最优选法的方案数。注意答案可能很大，请输出答案模 10^9+7 的结果。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品数量和背包容积。

接下来有 N 行，每行两个整数 v_i,w_i，用空格隔开，分别表示第 i 件物品的体积和价值。

输出格式 输出一个整数，表示方案数模 10^9+7 的结果。

数据范围 0<N,V≤1000 0<v_i,w_i≤1000

输入样例

输出样例：

二、题目解析

本题是 背包DP 中的经典题型 —— 【背包DP求最优方案总数】

01背包的转移方程f[i,j] = max(f[i - 1,j],f[i - 1,j - v] + w)

其中g[i,j] 是 f[i,j]取最大值的方案数

若f[i,j]是从f[i - 1,j]转移过来的，则g[i,j] = g[i - 1,j]

若f[i,j]是从f[i - 1,j - v] + w转移过来的，则g[i,j] = g[i - 1,j - v]

若f[i,j]均能从f[i - 1,j]和f[i - 1,j - v] + w转移过来的，则g[i,j] = g[i - 1,j] + g[i - 1,j - v]

将所有的最大值所对应的 方案数累加 在一起，即为 方案数总和

不超过

初始值和结果的收集，都应该从实际意义出发，根据状态表示的定义不同，进行初始化和收集答案。

初始值

先考虑最特殊的f[0],对应的二维表示就是f[0][0],即：在前0个物品中选择，空间不超过0的情况下

f[0]:在前0个物品中选择，空间最大是0，此时最大值是0，g[0] = 1，即此时方案数是1，什么都不能选，是唯一方案。
```
f[0] = 0, g[0] = 1;
```
再来考虑f[1],f[2],...f[m],对应的二维表示就是f[0][1],f[0][2],f[0][3],...f[0][m],即：在前0个物品中选择，空间不超过1,2,3,...m的情况下 f[1]:在前0个物品中选择，空间最多是1，最大值是0，方案数是1
```
for (int i = 1; i <= m; i++) f[i] = 0, g[i] = 1; //默认体积最大为i时方案数为1
```

答案因为本身定义就是 不超过i 的体积下，所以f[m]就是最大值，g[m]就是最大值时的方案数量。

恰好

考虑最特殊的f[0],对应的二维表示就是f[0][0],即：在前0个物品中选择，空间恰好是0的情况下。

f[0]:在前0个物品中选择，空间恰好是0，此时最大值是0，g[0] = 1，即此时方案数是1，什么都不能选，是唯一方案。
```
f[0] = 0, g[0] = 1;
```
再来考虑f[1],f[2],...f[m],对应的二维表示就是f[0][1],f[0][2],f[0][3],...f[0][m],即：在前0个物品中选择，空间恰好是1,2,3,...m的情况下。 f[1]:在前0个物品中选择，空间恰好是1，此时这是不可能满足条件的。最大值不存在，是不合法状态，同时，因为是预求最大，就设置成最小。f[i]=-INF.相应的，g[i]=0;
```
for (int i = 1; i <= m; i++) f[i] = -INF, g[i] = 0;
```
收集答案 因为本身定义就是 恰好i 的体积下，而最大值，未必就一定出现在恰好体积最大时，需要枚举一下所有空间，找出最大值，并且输出最大值对应方案数的 累加值。
```
int mx = 0, res = 0;
for (int i = 0; i <= m; i++) mx = max(mx, f[i]); //获取最大价值
for (int i = 0; i <= m; i++)
    if (mx == f[i]) res = (res + g[i]) % MOD; //等于最大价值的方案都添加

printf("%d\n", res);
```

三、空间最多为`i`的解法

二维写法

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

const int N = 1010, MOD = 1e9 + 7;
int f[N][N], g[N][N]; // f[j]、g[j]分别表示体积最大为j时的最大价值、方案数

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // 初始化，两个二维表，第一列比较特殊，可以进行初始化
    // f[0][0],g[0][0]
    // 在前0个物品中选择，空间最多为0，只能什么也不选择，最大值f[0][0]=0,方案数：g[0][0]=1
    f[0][0] = 0, g[0][0] = 1;
    // f[0][1~m],g[0][1~m]
    // 在前0个物品中选择，空间最多为1~m,最大值肯定是0，因为没的选择嘛，对应的方案数也是1
    for (int i = 1; i <= m; i++) f[0][i] = 0, g[0][i] = 1;

    // 从第二列开始吧
    for (int i = 1; i <= n; i++) { // 枚举每个物品，理解为阶段
        int v, w;
        scanf("%d %d", &v, &w);
        for (int j = 0; j <= m; j++) {                   // 枚举当前阶段可能的剩余体积
            int val = f[i - 1][j];                       // 在没选择当前物品前的最大价值
            if (j >= v) {                                // 如果剩余体积可以装得下第i个阶段的物品,选择与否可能会影响最大价值
                if (val > f[i - 1][j - v] + w) {         // 如果选择了当前物品还不如不选
                    f[i][j] = val;                       // 那还是用原来的最大价值吧
                    g[i][j] = g[i - 1][j];               // 个数也随着迁移吧
                } else if (val == f[i - 1][j - v] + w) { // 如果一样的价值呢？那就需要累加了
                    f[i][j] = val;
                    g[i][j] = (g[i - 1][j] + g[i - 1][j - v]) % MOD;
                } else {                           // 如果可以理新呢？
                    f[i][j] = f[i - 1][j - v] + w; // 更新最大值
                    g[i][j] = g[i - 1][j - v];     // 同步更新方案数量
                }
            } else { // 如果装不上，只能继承
                f[i][j] = val;
                g[i][j] = g[i - 1][j];
            }
        }
    }

    printf("%d\n", g[n][m]);
    return 0;
}

一维写法

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
const int MOD = 1e9 + 7;

int f[N], g[N];

int main() {
    int n, m;
    scanf("%d%d", &n, &m);

    f[0] = 0, g[0] = 1;

    for (int i = 1; i <= m; i++) f[i] = 0, g[i] = 1;

    for (int i = 1; i <= n; i++) {
        int v, w;
        scanf("%d%d", &v, &w);
        for (int j = m; j >= v; j--) {
            int val = f[j - v] + w;
            if (val > f[j]) {
                f[j] = val;
                g[j] = g[j - v];
            } else if (val == f[j])
                g[j] = (g[j] + g[j - v]) % MOD;
        }
    }

    printf("%d", g[m]);
    return 0;
}

四、空间恰好为`i`的解法

一维写法

#include <bits/stdc++.h>
using namespace std;
const int N = 1001;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
int f[N], g[N]; // f[j]、g[j]分别表示体积恰好为j时的最大价值、方案数

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

     // 1、考虑最特殊的f[0],对应的二维表示就是f[0][0],即：在前0个物品中选择，空间恰好是0的情况下。
    // f[0]:在前0个物品中选择，空间恰好是0，此时最大值是0，g[0] = 1，即此时方案数是1，什么都不能选，是唯一方案。
    f[0] = 0, g[0] = 1;

    //　2、再来考虑f[1],f[2],...f[m],对应的二维表示就是f[0][1],f[0][2],f[0][3],...f[0][m],即：在前0个物品中选择，空间恰好是1,2,3,...m的情况下。
    // f[1]:在前0个物品中选择，空间恰好是1，此时这是不可能满足条件的。最大值不存在，是不合法状态，同时，因为是预求最大，就设置成最小。f[i]=-INF.相应的，g[i]=0;
    for (int i = 1; i <= m; i++) f[i] = -INF, g[i] = 0;

    for (int i = 1; i <= n; i++) {
        int v, w;
        scanf("%d %d", &v, &w);
        for (int j = m; j >= v; j--) {
            int s = 0;
            int t = max(f[j], f[j - v] + w);
            if (t == f[j])
                s = (s + g[j]) % MOD; //添加不更新的方案
            if (t == f[j - v] + w)
                s = (s + g[j - v]) % MOD; //添加更新的方案

            f[j] = t;
            g[j] = s;
        }
    }

    //由于定义的状态表示是“空间恰好是i”，那么最大值的产生，可不一定存储在“空间恰好是m”的状态下，m及以下的各个状态，都可能装着最大值，
    //我们遍历一次f数组，找出最大值，然后二次遍历f数组、g数组,累加可以获得最大值时的方案数量。
    int mx = 0, res = 0;
    for (int i = 0; i <= m; i++) mx = max(mx, f[i]); //获取最大价值
    for (int i = 0; i <= m; i++)
        if (mx == f[i]) res = (res + g[i]) % MOD; //等于最大价值的方案都添加

    printf("%d\n", res);
    return 0;
}

二维写法

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9 + 7;
const int INF = 0x3f3f3f3f;
const int N = 1010;
int f[N][N], g[N][N]; // f[j]、g[j]分别表示体积恰好为j时的最大价值、方案数
int res;

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    // f[0][0],g[0][0]
    // 在前0个物品中选择，空间恰好是0，最大值f[0][0]=0,g[0][0]=1;
    f[0][0] = 0, g[0][0] = 1;

    // f[0][1~m],g[0][1~m]
    //　在前0个物品中选择，空间恰好是1~m，这是胡说，是不可能的，最大值是f[0][i]=-INF,g[0][i]=0
    for (int i = 1; i <= m; i++) f[0][i] = -INF, g[0][i] = 0;

    for (int i = 1; i <= n; i++) {
        int v, w;
        scanf("%d %d", &v, &w);
        for (int j = 0; j <= m; j++) {
            int val = f[i - 1][j];
            if (j >= v) {
                if (val > f[i - 1][j - v] + w) {
                    f[i][j] = val;
                    g[i][j] = g[i - 1][j];
                } else if (val == f[i - 1][j - v] + w) {
                    f[i][j] = val;
                    g[i][j] = (g[i - 1][j] + g[i - 1][j - v]) % MOD;
                } else {
                    f[i][j] = f[i - 1][j - v] + w;
                    g[i][j] = g[i - 1][j - v];
                }
            } else {
                f[i][j] = val;
                g[i][j] = g[i - 1][j];
            }
        }
    }
    //由于定义的状态表示是“空间恰好是i”，那么最大值的产生，可不一定存储在“空间恰好是m”的状态下，m及以下的各个状态，都可能装着最大值，
    //我们遍历一次f数组，找出最大值，然后二次遍历f数组、g数组,累加可以获得最大值时的方案数量。
    int mx = 0;
    for (int i = 0; i <= m; i++) mx = max(mx, f[n][i]);

    for (int i = 0; i <= m; i++)
        if (f[n][i] == mx) res = (res + g[n][i]) % MOD;

    printf("%d\n", res);
    return 0;
}

11 KiB Raw Permalink Blame History Unescape Escape

一、题目描述

二、题目解析

不超过

恰好

三、空间最多为i的解法

二维写法

一维写法

四、空间恰好为i的解法

一维写法

二维写法

11 KiB

Raw Permalink Blame History Unescape Escape

三、空间最多为`i`的解法

四、空间恰好为`i`的解法