今天做了查并集和 01 背包结合的一道题,致使我对背包开始了学习

# 前言

背包问题属于动态规划里面的一大块内容,包括九讲,本文主要讲 01 背包和完全背包

两个背包差别在于 01 背包每一个物品只能选一次,完全背包则可以选无限次,只要背包容积足够

# 01 背包

结合题目进行讲解

01 背包问题

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

第 ii 件物品的体积是 vi,价值是 wi。

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

# 输入格式

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

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

# 输出格式

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

# 数据范围

0<N,V10000<vi,wi10000<N,V≤1000 0<vi,wi≤1000

# 输入样例

4 5
1 2
2 4
3 4
4 5

# 输出样例:

8

# 分析

这是一道 01 背包模板题

首先从二维开始,我们用 dp [i] [j] 表示前 i 个物品当体积为 j 时最大收益,那么 dp[0][j]dp[i][0] 就都为 0,分别对应二维数组的第一行和第一列,接下来就从这两列一步一步往最后推,当碰到第 i 个物品,我们有两个选择,选或者不选,假若背包装不下,那么不选, dp[i][j]=dp[i-1][j] ,假若能装下,应该考虑装它是否能使利益最大化,所以应该在装和不装之间取大的, dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]) ,注意这里装不一定比不装收益高,因为可能前几件价值大,第 i 件价值小,选择了第 i 件就舍弃了前面价值大的。

详细分析点击我

# 代码

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN = 1e3+100;
const int MOD = 1e9;
int dp[MAXN][MAXN],w[MAXN],c[MAXN]; 
int main()
{
    ios;
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++) cin>>c[i]>>w[i];
    for(int i=1;i<=n;i++){
    	for(int j=1;j<=v;j++){
    		if(j>=c[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);
    		else dp[i][j]=dp[i-1][j];
            // 两种写法都一样
    	    //dp[i][j]=dp[i-1][j];
    		//if(j>=c[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-c[i]]+w[i]);            
		}
	}
	cout<<dp[n][v]<<endl;
	return 0;
}

# 降维

这个时间复杂的是 O (NV) 的,已经是最优了,但是空间还可以优化,观察上面的递推公式,当前前 i 个物品的状态只与前 i-1 个物品的状态有关,也就是在图上只与正上方和左上方有关,而这两个状态是已知的,因此可以用滚动数组从前往后推,也可以用一维数组从后往前推 ( 必须从后往前推,否则前一次循环保存下来的值将会被修改,从而造成推后面时用的值发生改变 )

# 代码

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int MAXN = 1e3+100;
const int MOD = 1e9;
int dp[MAXN],w[MAXN],c[MAXN]; 
int main()
{
    ios;
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++) cin>>c[i]>>w[i];
    for(int i=1;i<=n;i++){
    	for(int j=v;j>=c[i];j--){
    	   dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
		}
	}
	cout<<dp[v]<<endl;
	return 0;
}

# 完全背包

完全背包其实和 01 背包是超级相似的

其公式的推导可见闫式 DP 分析法,利用数学公式直接推出完全背包公式: dp[i][j]=max(dp[i-1][j],dp[i][j-w[i]]+v[i]) ,这个公式和 01 背包只有最后 max 第二部分的 i-1 换成了 i,当降维后,01 背包和完全背包就只有一个差别,倒着推和正着推😂

#include <stdio.h>
#include <iostream>
#include <string>
#include <string.h>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <vector>
#include <set>
#define ios ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define debug freopen("in.txt","r",stdin); freopen("out.txt","w",stdout)
using namespace std;
typedef long long ll;
const int N = 1e3+100;
const int MOD = 1e9;
int dp[N],w[N],c[N]; 
int main()
{
    ios;
    int n,v;
    cin>>n>>v;
    for(int i=1;i<=n;i++) cin>>c[i]>>w[i];
    for(int i=1;i<=n;i++){
        for(int j=c[i];j<=v;j++){
            dp[j]=max(dp[j],dp[j-c[i]]+w[i]);
        }
    }
	cout<<dp[v]<<endl;
	return 0;
}
更新于

请我喝[茶]~( ̄▽ ̄)~*

PocketCat 微信支付

微信支付

PocketCat 支付宝

支付宝