动态规划(Dynamic Programming)——背包问题

上烟雨心上尘

2024-03-14 帮助3人

动态规划(Dynamic Programming)

背包问题

01背包问题

动态规划

状态表示 f[i][j]
- 集合：所有考虑前i个物品，且体积不大于j的全部选法
- 属性：Max
状态计算：集合的划分

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

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

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

输入格式

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

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

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤10000<N，V≤1000
0<vi,wi≤10000< $v_i,w_i$ ≤1000

输入样例
4 5
1 2
2 4
3 4
4 5
输出样例：
8

二维

状态f[i][j]定义：前 i个物品，背包容量 j下的最优解（最大价值）

当背包容量够，需要决策选与不选第 i 个物品：

不选f[i][j] = f[i-1][j]
选f[i][j]=f[i-1][j-v[i]] w[i]
我们的决策是如何取到最大价值，因此以上两种情况取max()

代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N][N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;   i)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n;   i) {
        for (int j = 1; j <= m;   j) {
            f[i][j] = f[i - 1][j];
            if (v[i] <= j)  f[i][j] = max(f[i][j], f[i -1][j - v[i]]   w[i]);
        }
    }
    cout << f[n][m];
    return 0;
}

一维

我们定义的状态f[i][j]可以求得任意合法的i与j最优解，但题目只需要求得最终状态f[n][m]，因此我们只需要一维的空间来更新状态。

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010;
int v[N], w[N];
int f[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;   i)
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n;   i) {
        for (int j = m; j >= v[i]; --j) {
            
            
            f[j] = max(f[j], f[j - v[i]]   w[i]);
        }
    }
    cout << f[m];
    return 0;
}

完全背包问题

动态规划

状态表示 f[i][j]
- 集合：所有考虑前i个物品，且体积不大于j的全部选法
- 属性：Max
状态计算：集合的划分

f[i][j]第i个物品选了k个,先去掉k个物品i，再加回来k个物品i

f[i][j] = f[i-1][j-v[i]*k] w[i]*k

暴力dp

#include <iostream>

using namespace std;
const int N = 1010;
int f[N][N],v[N], w[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;   i) 
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n;   i) {
        for (int j = 1; j <= m;   j) {
            for (int k = 0; k * v[i] <= j;   k) {
                f[i][j] = max(f[i][j],f[i - 1][j - k * v[i]]   k * w[i]);
                // cout << f[i][j];
            }
        }
    }
    cout << f[n][m];
    return 0;
}

我们可以发现

f[i,j]=Max(f[i-1,j],f[i-1,j-v] w,f[i-1.j-2v] 2w,...,f[i-1.j-kv] kw

f[i,j-v]=Max( f[i-1,j-v],f[i-1.j-2v] w,...,f[i-1.j-kv] (k-1)w

代码

#include <iostream>
// #include <algorithm>
using namespace std;
const int N = 1010;
int f[N][N],v[N], w[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;   i) 
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n;   i) {
        for (int j = 1; j <= m;   j) {
            f[i][j] = f[i-1][j];
            if (j >= v[i])  f[i][j] = max(f[i][j], f[i][j-v[i]]   w[i]);           
        }
    }
    cout << f[n][m];
    return 0;
}

一维代码

#include <iostream>
// #include <algorithm>
using namespace std;
const int N = 1010;
int f[N],v[N], w[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;   i) 
        cin >> v[i] >> w[i];
    for (int i = 1; i <= n;   i) {
        for (int j = v[i]; j <= m;   j) {
            // f[i][j] = f[i-1][j];
            f[j] = max(f[j], f[j-v[i]]   w[i]);           
        }
    }
    cout << f[m];
    return 0;
}

多重背包问题

动态规划

状态表示 f[i][j]
- 集合：所有考虑前i个物品，且体积不大于j的全部选法
- 属性：Max
状态计算：集合的划分

题目描述

有 N 种物品和一个容量是 V 的背包。

第 i种物品最多有 $s_i$ 件，每件体积是 $v_i$ ，价值是 $w_i$ 。

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

输入格式

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

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

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100
0< $v_i$ , $w_i$ , $s_i$ ≤100

输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

代码

#include <iostream>
using namespace std;
const int N = 110;
int f[N][N], w[N], v[N], s[N];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;   i) 
        cin >> v[i] >> w[i] >> s[i];
    for (int i = 1; i <= n;   i)
        for (int j = 1; j <= m;   j) {
            for (int k = 0; k * v[i] <= j && k <= s[i];   k) {
                f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]]   k * w[i]);
            }
        }
    cout << f[n][m];
    return 0;
}

当数据范围扩大

数据范围

0<N≤1000

0<V≤2000

0< $v_i$ , $w_i$ , $s_i$ ≤2000

f(i, j) = Max(f(i-1,j),f(i-1,j-v) w,f(i-1,j-2v) 2w ... f(i-1,j-sv) sw)
f(i, j-v) = Max(f(i-1,j-v),f(i-1,j-2v) w,f(i-1,j-3v) 2w ... f(i-1,j-sv) (s-1)w,f(i, j) = Max(f(i-1,j),f(i-1,j-v) w,f(i-1,j-2v) 2w ... f(i-1,j-(s 1)v) sw)

所以不能用完全背包问题解决

我们可以采用二进制优化 01背包问题的方法

二进制优化

给出一堆苹果和10个箱子，选出n个苹果。将这一堆苹果分别按照1,2,4,8,16,…512分到10个箱子里，那么由于任何一个数字x∈[0,1023] (第11个箱子才能取到1024，评论区有讨论这个)都可以从这10个箱子里的苹果数量表示出来，但是这样选择的次数就是 ≤10次

代码

#include <iostream>
using namespace std;
const int N = 1e5   10;
int v[N], w[N];
int f[2020];
int main() {
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    while (n--) {
        int a, b, s;
        cin >> a >> b >> s;
        int k = 1;
        while (k <= s) {
            v[  cnt] = a * k;
            w[cnt] = b * k;
            s -= k;
            k *= 2;
        }
        if (s){
            v[  cnt] = a * s;
            w[cnt] = b * s;
        }
    }
    n = cnt;
    for (int i = 1; i <=n;   i) {
        for (int j = m; j >= v[i]; --j) {
            f[j] = max(f[j], f[j - v[i]]   w[i]);
        }
    }
    cout << f[m];
    return 0;
}

分组背包问题

有 N 组物品和一个容量是 V的背包。

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 $v_{i,j}$ ，价值是 $w_{i,j}$ ，其中 i 是组号，j 是组内编号。

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

输出最大价值。

输入格式

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

接下来有 N 组数据：

每组数据第一行有一个整数 $S_{i}$ ，表示第 i 个物品组的物品数量；

每组数据接下来有 $S_{i}$ 行，每行有两个整数 $v_{i,j}$ , $w_{i,j}$ ，用空格隔开，分别表示第 i个物品组的第 j 个物品的体积和价值；

输出格式

输出一个整数，表示最大价值。

数据范围

0<N,V≤100
0<Si≤100
0< $v_{i,j}$ , $w_{i,j}$ j≤100

输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：

8

代码

#include <iostream>
using namespace std;
const int N = 110;
int v[N], w[N];
int f[110];
int main() {
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n;   i) {
        int s;
        cin >> s;
        for (int j = 1; j <= s;   j) {
            cin >> v[j] >> w[j];
        }
        for (int k = m; k >= 1; --k) {
            for (int j = 1; j <= s;   j) {
                if (v[j] <= k)
                    f[k] = max(f[k], f[k - v[j]]   w[j]);
            }
        } 
    }
    cout << f[m];
    return 0;
}

这篇好文章是转载于：学新通技术网

动态规划(Dynamic Programming)——背包问题

动态规划(Dynamic Programming)

背包问题

01背包问题

输入格式

输出格式

数据范围

输入样例

输出样例：

二维

一维

完全背包问题

多重背包问题

输入格式

输出格式

数据范围

输入样例

输出样例：

数据范围

二进制优化

分组背包问题

输入格式

输出格式

数据范围

输入样例

输出样例：

photoshop保存的图片太大微信发不了怎么办

Android 11 保存文件到外部存储，并分享文件

word里面弄一个表格后上面的标题会跑到下面怎么办

《学习通》视频自动暂停处理方法

微信公众号没有声音提示怎么办

photoshop扩展功能面板显示灰色怎么办

excel下划线不显示怎么办

excel打印预览压线压字怎么办

怎样阻止微信小程序自动打开

photoshop蒙版画笔没反应怎么办