动态规划之背包问题

动态规划之背包问题

背包：01背包，完全背包，多重背包。

01背包：动态规划之背包问题基础。核心就是物品只能取一次。

完全背包：01背包PLUS版本，核心是物品可以无限取。

多重背包：01背包的PLUSSS版本，核心是物品i可以取k[i]次。

混合背包：就是合了上述三种背包。

分组背包：分成多组的背包。

01背包：

简单来说就是，给你一堆东西，每个东西最多能拿取一次，就是对于第i种物品，你可以选择将其放入背包中，也可以选择不放入。可以简化成这么一个题目：

给定n个物品，第i个物品的重量为weigh[i],价值为value[i]，现在给定一个容量为k的背包，，要求这个背包的所能装的最大价值。

已知第i个物品的重量为w[i],价值为v[i],以及背包的总容量为k。

假设DP状态dp(i,j)为在只能放前i个物品的情况下，容量为j的背包所能达到的最大总价值。接下来就是考虑如何状态转移。假设已经处理好了前i-1个物品的所有状态，如果第i个物品不放入背包，则背包容量不会变化，其内包含的价值也不会改变，如果第i个物品放入背包就会出现两种情况，可能是最大，也有可能是.也就是

当然了，如果数据比较大的话，二维数组可能会MLE，我们发现可能dp(i)只和dp(i-1)有关，所以可以利用滚动数组将他压缩到一维，就是

这样就可以了。代码实现如下：

#define int long long 
const int N=2e5+10;
int w[N],v[N],dp[N];
int k
for(int i=1;i<=n;i++){
    for(int j=k;j>=w[i];j++){
        dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
    }
}

例题：# P1048 [NOIP 2005 普及组] 采药

题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有一些不同的草药，采每一株都需要一些时间，每一株也有它自身的价值。我会给你一段时间，在这段时间里，你可以采到一些草药。如果你是一个聪明的孩子，你应该可以让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入

70 3
71 100
69 1
1 2

输出 #1

3

说明/提示

【数据范围】

• 对于 的数据，；
• 对于全部的数据，。

【题目来源】

NOIP 2005 普及组第三题

实现代码如下：

for(int i=1;i<=m;i++){
    for(int j=n;j>=1;j--){
       if(j-w[i]>=0) dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+v[i]);
       else dp[i][j]=dp[i-1][j];
    }
}

完全背包：

完全背包本质上和01背包差不多，但是它的其中一个物品可以选取无限次。

我们仍然假定，背包中前种物品的状态为，容量为j的背包所能够带来的最大价值。

同01背包一样，再假设第i种物品能选择k个。

但是这种的话会出现O()的时间复杂度，所以我们必须优化。很难想到可以优化成01背包的式子：

同理，可以优化成一维的

但是，完全背包的遍历和01背包是相反的(对于j的循环)。

看例题：

题目描述(p1616)

此题和原题的不同点：

. 每种草药可以无限制地疯狂采摘。

. 药的种类眼花缭乱，采药时间好长好长啊！师傅等得菊花都谢了！

输入格式

输入第一行有两个整数，分别代表总共能够用来采药的时间 和代表山洞里的草药的数目

第 到第 行，每行两个整数，第 行的整数 分别表示采摘第 种草药的时间和该草药的价值。

输出格式

输出一行，这一行只包含一个整数，表示在规定的时间内，可以采到的草药的最大总价值。

输入输出样例 #1

输入 #1

70 3
71 100
69 1
1 2

输出 #1

140

数据规模与约定

• 对于 的数据，保证 。
• 对于 的数据，保证 ，，且 ，。

for(int i=1;i<=n;i++){
    for(int j=w[i];j<=W;j++){
        if(dp[j-w[i]]+v[i]>dp[j])
        dp[j]=max(dp[j],dp[j-w[i]]+v[i])
     }
}

多重背包：

多重背包也是01背包的变种，指的是第种物品最多可以取次。

实际上这种背包能够完完全全地转化为01背包。在双层循环时再加一个

for(int m=0;m<=k[i];k++)

这样以来就解决了，状态转移方程如下：

同样的可以滚动数组来到一维。

代码实现如下：

for(int i=1;i<=n;i++){
    for(int j=W;j>=w[i];j--){
        for(int m=1;m*w[i]<=W&&m<=k[i];m++){
            dp[j]=max(dp[j],dp[j-k*w[i]]+k*v[i])
        }
    }
}

下面看例题：

P1833 樱花

题目描述

爱与愁大神后院里种了 棵樱花树，每棵都有美学值 。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。

输入格式

共 行：

第 行：现在时间 （几时：几分），去上学的时间 （几时：几分），爱与愁大神院子里有几棵樱花树 。这里的 ， 格式为：hh:mm，其中 ，，且 均为正整数。

第 行到第 行，每行三个正整数：看完第 棵树的耗费时间 ，第 棵树的美学值 ，看第 棵树的次数 （ 表示无数次， 是其他数字表示最多可看的次数 ）。

输出格式

只有一个整数，表示最大美学值。

输入输出样例 #1

输入 #1

6:50 7:00 3
2 1 0
3 3 1
4 5 4

输出 #1

11

说明/提示

数据：（即开始时间距离结束时间不超过 分钟），。保证 为同一天内的时间。

样例解释：赏第一棵樱花树一次，赏第三棵樱花树 次。

int dp[N];
int w[N],v[N],k[N];
void solve(){
    string s1,s2;
    cin>>s1>>s2>>n;
    for(int i=1;i<=n;i++){
        cin>>w[i]>>v[i]>>k[i];
    }
    auto check=[&](string s){
        for(int i=0;i<s.size();i++){
            if(s[i]==':') return i;
        }
    };
    auto summ=[&](string s){
        int q=check(s);
        if(q==1){
            return (s[0]-'0')*60+(s[2]-'0')*10+s[3]-'0';
        }else{
            return ((s[0]-'0')*10+s[1]-'0')*60+(s[3]-'0')*10+s[4]-'0';
        }
    };
    auto trans=[&](string s1,string s2){
        int res1=summ(s1);
        int res2=summ(s2);
        return res2-res1;
    };
    int T=trans(s1,s2);
    for(int i=1;i<=n;i++){
        if(k[i]==0){
            for(int j=w[i];j<=T;j++){
                dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
            }
        }else{
        for(int j=1;j<=k[i];j++){
            for(int l=T;l>=w[i];l--){
                dp[l]=max(dp[l],dp[l-w[i]]+v[i]);
                }
            }
        }
    }
    cout<<dp[T]<<endl;
}

混合背包：

（上面那个题就是混合背包）实际上就是把上面三个背包：01背包，完全背包和多重背包结合起来了。处理的方式也是很简单：

for(int i=1;i<=n;i++){
    if(满足01背包的条件){
        for(int j=w[i];j<=W;j++){
            ......
        }
    }
    else if(满足完全背包的条件){
        for(int j=W;j>=w[i];j--){
            ......
        }
    }
    else{//剩下的就是多重背包
        for(int j=1;j<=k[i];j++){
            for(int m=W;m>=w[i]*j;m--){
                ......
            }
        }        
    }
}

只用分部枚举这三种背包的模式就可以了。

分组背包：

分组背包中的物品通常是有写属于那个背包的，我们不妨先输入所有的物品后，再根据其种类再分别在该种类中取其中一件。然后就转变成了01背包。

首先是如何存储组数：

vector<vector<pair<int,int>>> v(101);
for(int i=1;i<=n;i++){
    int w,val,k//占地，价值，组别
    v[k].pb({w,val});
}

例题：

P1757 通天之分组背包

题目背景

直达通天路·小 A 历险记第二篇

题目描述

自 背包问世之后，小 A 对此深感兴趣。一天，小 A 去远游，却发现他的背包不同于 背包，他的物品大致可分为 组，每组中的物品相互冲突，现在，他想知道最大的利用价值是多少。

输入格式

两个数 ，表示一共有 件物品，总重量为 。

接下来 行，每行 个数 ，表示物品的重量，利用价值，所属组数。

输出格式

一个数，最大的利用价值。

输入输出样例 #1

输入 #1

45 3
10 10 1
10 5 1
50 400 2

输出 #1

10

说明/提示

，，， 在 int 范围内。

代码如下：

void solve(){
    cin>>m>>n;
    vector<vector<pair<int,int>>> v(101);
    for(int i=1;i<=n;i++){
        int w, val, k;
        cin>>w>>val>>k;
        v[k].pb({w,val});
    }
    for(int k=1;k<=100;k++){
        for(int i=m;i>=0;i--){
            for(auto [w,val]:v[k]){
                if(i>=w){
                    dp[i]=max(dp[i],dp[i-w]+val);
                }
            }
        }
    }
    cout<<dp[m]<<endl;
}