动态规划-背包问题

​

关于动态规划的背包问题，可分为
（1）0/1背包问题
（2）分组背包问题
（3）多重背包问题
（4）完全背包问题

（1）0/1背包问题。

问题描述：有NN件物品和一个容量是 VV的背包。每件物品只能使用一次。
第 ii件物品的体积是 vivi，价值是wi wi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输入描述：第一行两个整数，N,V 用空格隔开，分别表示物品数量和背包容积。
接下来有N行，每行两个数vi，wi，用空格分隔开，表示该物体的体积和价值。
N，V
输出描述： 输出一个整数，表示最大价值。
分析
引入一个(N+1)*(V+1)的二维数组dp[ ][ ]。
dp[i][j]表示把前i个物品【1，i】装入容量为j的背包中获得最大价值
把每个dp[i][j]都看做一个背包；容量为j，装1~i这些物品，最后的dp[N][V]为问题答案。
dp转移方程：
(1)、第i个物品的体积比容量j还大，不能装进背包。直接继承前 i-1 个物品装进容量为j的背包情况即可，即dp[i][j]=dp[i-1][j]。
(2)、第i个物品的体积比容量j小，能装进背包，又可以分成两种情况：装或不装：
①装第i个物品。从前i-1个物品推广，前i-1个物品价值为dp[i-1][j]。第i个背包装进背包后，背包容量减少v[i]，价值增加w[i]
有dp[i][j]=dp[i-1][j-v[i]]+w[i]。
②不装第i个物品，有dp[i][j]=dp[i-1][j]。
取两者的最大值:
dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i])
递推代码（暴力做法）：
参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], v[N]; //物品的价值和体积
int dp[N][N];
int solve(int n, int V) {
    for (int i = 1; i <= n; i++)
        for (int j = 0; j <= V; j++) {
            if (v[i] > j)
                dp[i][j] = dp[i - 1][j];  //第i个物品比背包大，装不了。
            else
                dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]); //第i个物品能装。
        }
    return dp[n][V];
}
int main() {
    int n, V;
    scanf("%d%d", &n, &V);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    printf("%d", solve(n, V));
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

记忆化搜索（暴力做法）：
参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int w[N], v[N];
int dp[N][N];
int solve(int i, int j) {
    if (dp[i][j] != 0)
        return dp[i][j];
    if (i == 0)
        return 0;
    int res;
    if (v[i] > j)
        res = solve(i - 1, j);
    else
        res = max(solve(i - 1, j), solve(i - 1, j - v[i]) + w[i]);
    return dp[i][j] = res;
}
int main() {
    int n, V;
    scanf("%d%d", &n, &V);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    printf("%d", solve(n,V);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

dp[i][]只与dp[i-1][]有关，与其他没有关系。
使用覆盖。
有如下两种方式：
(1)交替滚动：
定义dp[2][j]，用dp[0][ ]和dp[1][ ]交替滚动。
在如下代码中，now指向正在计算的最新一行，old指向已经计算过的旧的一行。
在递推关系中，now相当于i，old相当于i-1。

int dp[2][N];
int solve(int n, int V) {
    int now=0,old=1;  
    for(int i=1;i<=n;i++)
    {
        swap(old,now);  //交替转换
        for(int j=0;j<=V;j++)
        {
            dp[now][j]=dp[old][j];
            if(v[i]<=j)
            dp[now][j]=max(dp[old][j],dp[old][j-v[i]]+w[i]);
        }
    }
    return dp[now][V]; //返回最新的行
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完整代码为：

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010;
int dp[2][N];
int v[N], w[N];
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    int old = 1, ne = 0;
    for (int i = 1; i <= n; i++) {
        swap(old, ne);//交替上一列与下一列
        for (int j = 1; j <= m; j++) {
            dp[ne][j] = dp[old][j]; //将旧状态转移
            if (v[i] <= j)
                dp[ne][j] = max(dp[ne][j], dp[old][j - v[i]] + w[i]);
        }
    }
    printf("%d", dp[ne][m]);//输出新状态
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

(2)自我滚动：
原理和上述类似

int dp[N];
int solve(int n,int V)
{
    for(int i=1;i<=n;i++)
    for(int j=V;j>=v[i];j--)
    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    return dp[V];
}
1
2
3
4
5
6
7
8

此时代码为：

#include <bits/stdc++.h>
using namespace std;
int n, m;
const int N = 1010;
int dp[N];
int v[N], w[N];
int main() {
    scanf("%d%d", &m, &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &v[i], &w[i]);
    for (int i = 1; i <= n; i++) {
        for (int j = m; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    }//自我滚动数组
    printf("%d", dp[m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

（2）分组背包问题。

问题描述： 有N组物品和一个容量是V的背包。
每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vik ，价值是 wik，其中i是组号，k是组内编号。
求解将哪些物品装入背包，可使物品总体积不超过背包容量，且总价值最大。
输入描述：第一行有两个整数 N,V，用空格隔开，分别表示物品组数和背包容量。
接下来有N组数据：
每组数据第一行有一个整数Si，表示第 i个物品组的物品数量；
每组数据接下来有Si行，每行有两个整数 vik，wik，用空格隔开，分别表示第 i个物品组的第k个物品的体积和价值
输出格式：
输出一个整数，表示最大价值。
分析：
定义一个状态dp[i][j],表示把前i组的物品装进容量为j的背包（每个组里最多选一个物品）里可获得的最大价值。
状态转义方程：
dp[i][j]=max{dp[i-1][j],dp[i-1][j-v[i][k]]+w[i][k]}
其中dp[i-1][j]表示第 i 组不选择物品。dp[i-1][j-c[i][k]]表示第i组的第k个物品，求解方程需要i，j，k三重循环。
若改为转动数组则状态转移方程为：
dp[j]=max{dp[j],dp[j-c[i][k]]+w[i][k]}

参考代码：
（一）

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int n,m;
int dp[N],v[N],w[N];
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=0;i<n;i++)
    {
        int num; //第i+1组的物品个数
        scanf("%d",&num);
        for(int j=1;j<=num;j++)
        scanf("%d%d",&v[j],&w[j]); //第i组num个物品的体积和价格。
        for(int j=m;j>=0;j--)
            for(int k=1;k<=num;k++)
            if(j>=v[k])
            dp[j]=max(dp[j],dp[j-v[k]]+w[k]);  //小阶段DP，通过状态方程来表示第i组第k个物品选不选择
    }
    printf("%d",dp[m]);
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

(二)

#include<bits/stdc++.h>
using namespace std;
const int N=110;
int v[N][N],w[N][N],num[N];//以v[i][j]为例子，i表示第i组，j表示第i组里的第j个，w[i][j]同理。num[i]中i表示组别
//num[i]表示第i组内物品个数
int dp[N];
int n,sum;
int main()
{
    cin>>n>>sum;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
        for(int j=1;j<=num[i];j++)
        cin>>v[i][j]>>w[i][j];
    }
    for(int i=1;i<=n;i++)
    for(int j=sum;j>=0;j--)
    for(int k=0;k<=num[i];k++)
    if(j>=v[i][k])
    dp[j]=max(dp[j],dp[j-v[i][k]]+w[i][k]);
    cout<<dp[sum];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（3）多重背包问题。

问题描述：有一个最大载重为 W 的采集车，洞穴里总共有 n 种宝物，每种宝物的价值为 vi，重量为 wi，每种宝物有 mi 件。希望在采集车不超载的前提下，选择一些宝物装进采集车，使得它们的价值和最大。
输入描述：
第一行为一个整数 n 和 W，分别表示宝物种数和采集车的最大载重。
接下来 n 行每行三个整数 vi,wi,mi。
输出描述：
输出最大宝物价值
分析：
将m件物品看成一件不同的物品，转化成0/1背包问题。
参考代码：
基础暴力版本（三重循环，时间一般会爆掉）

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int n, sum;   //n为物品种类数，sum为背包总体积
int dp[N], w[N], v[N], num[N];//dp[i]为在背包容量为i的情况下的最大价值，w[i]为第i个物品的价值，v[i]为第i个物品的体积
//num[i]为第i个物品的数量
int main() {
    cin >> n >> sum;  
    for (int i = 1; i <= n; i++)
        cin >> v[i]>>w[i] >> num[i];
    for (int i = 1; i <= n; i++) //在第i种物品选择
            for (int j = sum;j >=v[i]; j--)  //dp操作
                    for (int k = 1;j >= k * v[i]&&k <= num[i]; k++)
                dp[j] = max(dp[j], dp[j - v[i] * k] + w[i] * k);
    cout << dp[sum];//输出结果
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

二进制优化版本：
数学规律：每个数都可以由以下部分来组成
num=an2^n+a(n-1)*2(n-1)…+a12+a0
根据这个规律，任意一个数可从1、2、4、8…（称这些数为二次幂升序）以及一个多余项（多余项的产生是由于1、2、4、8等有序排列中中间的某几项缺少而导致的）组成。
每个数都可由二次幂升序排列的数来组成，相比较num个数字，其二进制表示可以大大降低时间复杂度。
所以思路就是把二次幂升序和多余项看成一种物品的选择，之后0/1背包问题处理问题

#include<bits/stdc++.h>
using namespace std;
const int N=11010,M=2010;
int dp[M];
int v[N],w[N];
int n,sum;
int main()
{
    cin>>n>>sum;
    int all=0;
    for(int i=1;i<=n;i++)
    {
        int a,b,c;
        cin>>a>>b>>c;
        for(int k=1;k<=c;k*=2)
        {
            all++;
            v[all]=a*k;
            w[all]=b*k;
            c-=k;
        }
        if(c>0)
        {
            all++;
            v[all]=a*c;
            w[all]=b*c;
        }
    }
    n=all;
    for(int i=1;i<=n;i++)
    for(int j=sum;j>=v[i];j--)
    dp[j]=max(dp[j],dp[j-v[i]]+w[i]);
    cout<<dp[sum];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

(4)完全背包问题。

问题描述：现有N种物品和一个最多能承重M的背包，每种物品都有无限个，第i种物品的重量是wi，价值是vi。在背包能承受的范围内，试问将哪些物品装入背包后可使总价值最大，求这个最大价值。
分析：
这道题的思路我个人觉得有两种：（个人看法）
一种就是把完全背包问题转化成多重背包问题，因为物品虽然是无限个，但能装进去的个数是有限多个，不妨将能装进1个、2个、3个。。。。。。利用二进制优化来操作，最后变成0/1背包问题。（这个是我个人自己结合二进制优化自己想出来的，不是标准正解）
参考代码：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010, M = 11010;
int v[M], w[M];
int dp[N];
int n, sum;
int all;
int main() {
    cin >> n >> sum;
    for (int i = 1; i <= n; i++) {
        int t; //存储最多能放多少东西
        int a, b; //a代表物品体积，b代表物品价值
        cin >> a >> b; 
        t = sum / a; //计算存储数量
        for (int k = 1; k <= t; k *= 2) { //二进制优化
            all++;
            v[all] = a * k;
            w[all] = b * k;
            t-= k;
        }
        if (t > 0) { //对多余处理
            all++;
            v[all] = a * t;
            w[all] = b * t;
        }
    }
    n = all; //转化
    for (int i = 1; i <= all; i++) //简单的0/1背包
        for (int j = sum; j >= v[i]; j--)
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
    cout << dp[sum];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

另一种是观察后对状态方程的优化（正解）
以此为例子，观察:
dp[2][5]=max(dp[1][5]、dp[1][3]+w,dp[1][1]+2w);
dp[2][3]=max(dp[1][3],dp[1][1]+w);
dp[2][1]=dp[1][1];
（可能不是很标准，但意思到位就行啦）
观察以上操作，不难发现。
dp[2][3]=max(dp[1][3],dp[1][1]+w)=max(dp[1][3],dp[2][1]+w);
dp[2][5]=max(dp[1][5]、dp[1][3]+w,dp[1][1]+2w)=max(dp[1][5],dp[2][3]+w)
由此可以得到：
dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);
其中j是从小到大。
参考代码：

 #include<bits/stdc++.h>
using namespace std;
const int N=1010;
int dp[N];
int v,w;
int n,sum;
int main()
{
    cin>>n>>sum;
    while(n--)
    {
        cin>>v>>w;
        for(int j=v;j<=sum;j++)
        dp[j]=max(dp[j],dp[j-v]+w);
    }
    cout<<dp[sum];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

​