DP——背包问题

背包问题

N 件物品放入容量为 V 的背包，求最大的价值。
常见的背包问题分为：01背包问题，完全背包问题。
其中核心的问题还是 01背包问题，其余的背包问题都是基于01背包的变形。

AcWing 2. 01背包问题

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

第 i 件物品的体积是 vi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0 0

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

8

在这里插入图片描述
优化一般就是优化状态转移方程

01背包
特点:每个物品仅能使用一次
重要变量&公式解释
f[i][j]:表示所有选法集合中,只从前i个物品中选,并且总体积≤j的选法的集合,它的值是这个集合中每一个选法的最大值.
状态转移方程
f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i])

集合的划分，原则：选不选最后一个物品，分为两种

  1. f[i-1][j]:不选第i个物品的集合中的最大值
  2. f[i-1][j-v[i]]+w[i]:选第i个物品的集合,但是直接求不容易求所在集合的属性

集合如何划分
一般原则:不重不漏,不重不一定都要满足(一般求个数时要满足)
如何将现有的集合划分为更小的子集,使得所有子集都可以计算出来.

普通代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[[0 for i in range(0,m+1)] for i in range(0,n+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(0,m+1):
        dp[i][j]=dp[i-1][j]
        if j>=v[i]:
            dp[i][j]=max(dp[i][j],dp[i-1][j-v[i]]+w[i])

print(dp[n-1][m])

优化代码

很多的DP问题可以在空间上进一步的优化，即对原来的状态计算进行等价变形。

观察状态转移方程 f[i][j]=max{f[i-1][j], f[i-1][j-v[i]]+w[i]} 可以发现：

当前层的状态永远只依赖于上一层的状态，因此我们可以用户一维的状态 f[j] 来表示之前同样的状态。

在第 i次循环之前，f[j]=f[i-1][j]

在第 i次循环之后，f[j]=f[i][j]

因此我们的状态转移方程变为了 f[j]=max{f[j], f[j-v[i]]+w[i]}

注意：由于我们要保证 f[j-v[i]] 就相当于原来的 f[i-1][j-v[i]] ，所以我们的第二层循环需要改为逆序。

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[0 for i in range(0,m+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(m,v[i]-1,-1):
        dp[j]=max(dp[j],dp[j-v[i]]+w[i])

print(dp[m])

AcWing 3. 完全背包问题

有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 ii 种物品的体积是 vi，价值是 wi。

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

输入格式

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

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

输出格式

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

数据范围

0 0

输入样例

4 5
1 2
2 4
3 4
4 5

输出样例：

10

基本代码

状态表示 f[i][j]：
集合：所有满足只从前i个物品选，总体积不超过j的方案的集合。
属性：Max

状态计算:
集合划分
选0个，选1个，选2个，选3个，...，选k个，...，选无穷个。

选k个：

\[f[i][j] = max(f[i-1][j],f[i-1][j-v] + w,f[i-1][j-2v]+2w,......) \]

\[f[i][j-v] = max(f[i-1][j-v],f[i-1][j-2v] + w,f[i-1][j-3v]+2w,......) \]

合并一下 f[i][j] = max(f[i-1][j] ， f[i][j-v] + w）;

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[[0 for i in range(0,m+1)] for i in range(0,n+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(0,m+1):
        dp[i][j]=dp[i-1][j]
        if j>=v[i]:
            dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i])
print(dp[n-1][m])

优化代码

import sys,math
sys.setrecursionlimit(10**9)
from collections import defaultdict
 
IA = lambda: map(int,input().split())
IAS= lambda: map(str,input().split())

n,m=map(int,input().split())
v=[0 for i in range(0,n+1)]
w=[0 for i in range(0,n+1)]
dp=[0 for i in range(0,m+1)]

for i in range(0,n):
    v[i],w[i]=map(int,input().split())

for i in range(0,n):
    for j in range(v[i],m+1):
            dp[j]=max(dp[j],dp[j-v[i]]+w[i])
print(dp[m])

AcWing 4. 多重背包问题 I

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

第 i 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

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

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

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

数据范围
0 0 输入样例
4 5
1 2 3
2 4 1
3 4 3
4 5 2
输出样例：
10

题解

状态表示 f[i][j]：
集合：所有满足只从前i个物品选，总体积不超过j的方案的集合。
属性：Max

状态计算:
集合划分
选0个，选1个，选2个，选3个，...，选k个，...，选s[i]个。

\[f[i][j] = max(f[i-1][j], f[i][j - k*v[i]]+w[i] *k), k = 0,1,2,3,...,s[i] \]

#include
using namespace std;
const int N = 100005;
int dp[N],v[N],w[N],s[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; i++)
    {
        scanf("%d%d%d",&v[i],&w[i],&s[i]);
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= 0; j --)
        {
            for(int k = 0; j >= k * v[i] && k <= s[i]; k++)
            {
                
                dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
            }
            
        }
    }
    cout<

AcWing 5. 多重背包问题 II

题目描述：多重背包问题II
有 N种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 ii 种物品最多有 si 件，每件体积是 vi，价值是 wi。

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

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

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

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

数据范围
0 0 0

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

多重背包的优化

首先，我们不能用完全背包的优化思路来优化这个问题，因为每组的物品的个数都不一样，是不能像之前一样推导不优化递推关系的。

我们列举一下更新次序的内部关系：

 f[i , j ] = max( f[i-1,j] , f[i-1,j-v]+w , f[i-1,j-2*v]+2*w , f[i-1,j-3*v]+3*w , ...,f[i-1][j-sv] + sw) 
 f[i , j-v]= max(            f[i-1,j-v] , f[i-1,j-2*v] + w , f[i-1,j-3*v]+2*w , ...，,f[i-1][j-(s+1)v] + sw)

max无法做减法，所以不可以用完全背包方式优化。

二进制优化的方法
假设s = 1023（2^10-1)
我们可以用1，2，4，8，...,512 (2^9） 来组合成0~1023，枚举10次。
即\(2^0,2^1,.... ,2^k\)可以表示所有\(0 -2^{k+1}\)里面的数

总结：
给我们S个物品，我们可以拆分打包成logS物品，就变成01背包问题。
即\(1，2，4，8，...，2^k，C （C= S- sum(1,2^k)<2^{k+1})\)
拼成0~2^(k+1)

代码

#include
using namespace std;
const int N = 100005;
int v[N], w[N], dp[N];
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    int cnt = 1;
    int V, W, S;
    for(int i = 1;i <= n;i++)
    {
        scanf("%d%d%d", &V, &W, &S);
        
        int k = 1;
        while(k <= S)
        {
            v[cnt] = V * k;
            w[cnt++] = W * k;
            S -= k;
            k *= 2;
        }
        if(S > 0)
        {
            v[cnt] = V * S;
            w[cnt++] = W * S;
        }
        
    }
    for(int i = 1;i < cnt; i++)
    {
        for(int j = m; j >= v[i]; j--)
        {
            dp[j] = max(dp[j], dp[j - v[i]] + w[i]);
        }
    }
    printf("%d\n", dp[m]);
    
    return 0;
}

AcWing 9. 分组背包问题

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

每组物品有若干个，同一组内的物品最多只能选一个。
每件物品的体积是 vij，价值是 wij，其中 i 是组号，j 是组内编号。

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

输出最大价值。

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

接下来有 N 组数据：

每组数据第一行有一个整数 Si，表示第 i 个物品组的物品数量；
每组数据接下来有 Si 行，每行有两个整数 vij,wij，用空格隔开，分别表示第 i 个物品组的第 j 个物品的体积和价值；

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

数据范围
0 0 0 输入样例
3 5
2
1 2
2 4
1
3 4
1
4 5
输出样例：
8
题目考点
动态规划

解题思路

状态表示：f[i][j]

  1. 集合：从前i组物品中选,且总体积不超过j的所有方案的集合.
  2. 属性：最大值

状态计算：

  1. 思想-----集合的划分
  2. 集合划分依据：根据从第i组物品中选哪个物品进行划分.
    f[i][j] = max(f[i][j], f[i - 1][j - v[i][k]] + w[i][k]);

代码

#include
using namespace std;
const int N = 1005;
int v[N][N], w[N][N], dp[N],s[N];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for(int i = 1;i <= n; i++)
    {
    
        scanf("%d", &s[i]);
        for(int j = 1; j <= s[i]; j++)
        {
            scanf("%d%d", &v[i][j], &w[i][j]);
        }
    }
    
    for(int i = 1; i <= n; i++)
    {
        for(int j = m; j >= 0; j--)
        {
            for(int k = 1; k <= s[i]; k++)
            {
                if(v[i][k] <= j)
                {
                    dp[j] = max(dp[j], dp[j - v[i][k]] + w[i][k]);
                }
            }
        }
    }
    
    printf("%d", dp[m]);
    return 0;
}
算法DP

相关

如何实现LRU（最近最少使用）缓存淘汰算法？

2021.11.16（各排序算法对比）

react dom移动算法

DP决策优化小结

dp专题练习

算法第四章上机实验报告

算法第二章实践报告

【莫队算法】

算法第四章实践报告

腾讯云搭建个人博客wordpress

关于tarjan算法的一些整理

dp多维状态的优化

标签