python

6.7 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.

背包问题-方案数-空间至多`j`

一、`01`背包

例子：给你一堆物品，每个物品有一定的体积，每个物品只能选一个，求总体积 不超过m的 方案数。

求方案数，没有价值累加的概念。

输入

//物品个数　体积
//每个物品的体积
4 5
2 2 3 7

输出

理解一下

一个都不选
a[0]
a[1]
a[2]
a[0]+a[1]
a[0]+a[2]
a[1]+a[2]

1、二维

#include <bits/stdc++.h>

using namespace std;
const int N = 110;

int n, m;
int f[N][N];//第一维：前i个物品，第二维：体积j及以下

int main() {
    scanf("%d %d",&n,&m);
    //初始化,在前0个物品中选，所有合法空间，都有一种结果，就是啥也不要，啥也不要也满足“不超过j”这个条件，方案数=1。
    for (int i = 0; i <= m; i++) f[0][i] = 1;

    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d",&v);
        for (int j = 0; j <= m; j++) {
            f[i][j] = f[i - 1][j];//不被i件物品
            if (j >= v) f[i][j] += f[i - 1][j - v];//能装下就要加上可以转移过来状态的方案数
        }
    }
    printf("%d\n",f[n][m]);
    return 0;
}

2、一维

#include <bits/stdc++.h>

using namespace std;
const int N = 110;

int n, m;
int f[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= m; i++) f[i] = 1;

    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d",&v);
        for (int j = m; j >= v; j--) f[j] += f[j - v];
    }
    printf("%d\n",f[m]);
    return 0;
}

二、完全背包

例子：给你一堆物品，每个物品有一定的体积，每个物品可以选无数多个，求总体积不超过m的 方案数

输入

3 5
2 3 7

输出

理解一下：

一个都不选
a[0]
a[0]*2
a[1]
a[0]+a[1]

共5种方案。

1、二维

#include <bits/stdc++.h>

using namespace std;
const int N = 110;

int n, m;
int f[N][N];

int main() {
    //文件输入
    freopen("ZhiDuo_WQ.in", "r", stdin);

    scanf("%d %d", &n, &m);
    for (int i = 0; i <= m; i++) f[0][i] = 1; //前0种物品中选择，最多不超过m的体积下，选择的方案只有一种合法，就是啥也不选
    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d", &v);
        /*写法1*/
        for (int j = 0; j <= m; j++) {
            if (j >= v)
                f[i][j] = f[i - 1][j] + f[i][j - v];
            //注意这里与01背包的差别！！！
            //　在01背包的状态转移中，i就是i,它之前不能出现过i,只能从i-1转移
            //　在完全背包的状态转移中，i出现过没关系，只要能装下，出现几个都行，可以从i转移
            // 01背包：
            // f[i][j] = f[i - 1][j] + f[i - 1][j - v];
            else
                f[i][j] = f[i - 1][j];
        }

        /*写法2*/
        // for (int j = 0; j <= m; j++) {
        //     f[i][j] = f[i - 1][j];
        //     if (j >= v) f[i][j] += f[i][j - v];
        // }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

2、一维

#include <bits/stdc++.h>

using namespace std;
const int N = 110;

int n, m;
int f[N];

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= m; i++) f[i] = 1;
    for (int i = 1; i <= n; i++) {
        int v;
        scanf("%d",&v);
        //完全背包
        for (int j = v; j <= m; j++) f[j] += f[j - v];
        //对比01背包
        //for (int j = m; j >= v; j--) f[j] += f[j - v];
    }
    printf("%d\n",f[m]);
    return 0;
}

练习题洛谷 P1832

欧筛下标从1开始

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e3 + 5;

LL f[N][N];

//欧拉筛,下标从1开始
//这个欧拉筛黄海修改过，修改下标从1开始
int primes[N], st[N], cnt;
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[++cnt] = i;
        for (int j = 1; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    int m;
    scanf("%d", &m);
    get_primes(m); // 1 ~ m以内有cnt个素数

    int n = cnt;
    for (int i = 0; i <= n; i++) f[i][0] = 1; //初始化，如果刚好只可以选一个数，即j == primes[i]，那么只有一种方案。

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            /*
            // j足够大，那么对于一个素数可以选，或是不选。两种方案要求总和。
            if (j >= primes[i])
                f[i][j] = f[i - 1][j] + f[i][j - primes[i]];
            else
                f[i][j] = f[i - 1][j]; // j不够大，只有不选这一种方案。
            */

            //与上面的代码是等价的，一样可以AC
            f[i][j] = f[i - 1][j];
            if (j >= primes[i]) f[i][j] += f[i][j - primes[i]];
        }
    }
    printf("%lld\n", f[n][m]);
    return 0;
}

欧筛下标从0开始

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e3 + 5;

LL f[N][N];

//欧拉筛
int primes[N], st[N], cnt;
void get_primes(int n) {
    for (int i = 2; i <= n; i++) {
        if (!st[i]) primes[cnt++] = i;
        for (int j = 0; primes[j] * i <= n; j++) {
            st[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
}

int main() {
    int m;
    scanf("%d", &m);
    get_primes(m); // 1 ~ m以内有cnt个素数

    int n = cnt;
    for (int i = 0; i <= n; i++) f[i][0] = 1; //初始化，如果刚好只可以选一个数，即j == primes[i]，那么只有一种方案。

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            /*
            // j足够大，那么对于一个素数可以选，或是不选。两种方案要求总和。
            if (j >= primes[i])
                f[i][j] = f[i - 1][j] + f[i][j - primes[i]];
            else
                f[i][j] = f[i - 1][j]; // j不够大，只有不选这一种方案。
            */

            //与上面的代码是等价的，一样可以AC
            f[i][j] = f[i - 1][j];
            if (j >= primes[i - 1]) f[i][j] += f[i][j - primes[i - 1]];
        }
    }
    printf("%lld\n", f[n][m]);
    return 0;
}

6.7 KiB Raw Permalink Blame History Unescape Escape

背包问题-方案数-空间至多j

一、01背包

1、二维

2、一维

二、完全背包

1、二维

2、一维

6.7 KiB

Raw Permalink Blame History Unescape Escape

背包问题-方案数-空间至多`j`

一、`01`背包