参考:背包九讲$9.5$。

github传送门

直接下载pdf

以上为课件资料。


题目传送门

题意:求01背包前$k$优解的价值和。策略不同但价值相同视为不同方案。要求背包必须装满。

算法时间复杂度:$O(VNK)$。

考虑01背包的最优解。$c$即$cost$(花费),$v$即$value$(价值)。

$$ dp[i][j]=max\{dp[i-1][j],dp[i-1][j-c[i]]+v[i]\} $$

既然是$k$优解,那么就用$dp[i][j][k]$来表示吧!

此时,我们如果再把$dp[i][j]$看作是一个状态的话,那么这个状态存储的就是一个$[1...k]$的序列。表示从最优解到$k$优解。很明显,这样一个正常的序列应该是单调递减的。

带着$dp[i][j]$状态是一个单调递减序列的认识,我们再来看看上面的递推式。

如果全部选择了前一项,那么新的序列就是$dp[i-1][j]$。

如果全部选择了后一项,那么新的序列就是$dp[i-1][j-c[i]]$的每一项加上$v[i]$。

为了保证我们新的序列是前k解,这两个选择带来的$2k$项,我们选择更优的前$k$项即可。

并且因为两个序列都是单调递减的序列,这一步只需要$O(k)$。

于是就在普通$01$背包的$dp[V]$上增一维$dp[V][K]$即可,从原本每一步$O(1)$的取$max$变成$O(k)$的转移序列。总时间复杂度就是$O(VNK)$。

代码实现出奇简单...

#include<bits/stdc++.h>
using namespace std;
const int N=210;
const int V=5010;
const int K=55;
int c[N],v[N];
int dp[V][K];//容量为v时的k优解
int qu[K];//临时存放序列
int main()
{
    int k,m,n;
    scanf("%d%d%d",&k,&m,&n);
    for(int i=1;i<=n;i++)
        scanf("%d%d",&c[i],&v[i]);
    memset(dp,-0x3f,sizeof dp);
    dp[0][1]=0;
    for(int i=1;i<=n;i++)
        for(int j=m;j>=c[i];j--)
        {
            for(int l=1,f1=1,f2=1;l<=k;l++)
                qu[l]=(dp[j][f1]>dp[j-c[i]][f2]+v[i])?dp[j][f1++]:dp[j-c[i]][f2++]+v[i];
            for(int l=1;l<=k;l++)
                dp[j][l]=qu[l];
        }
    int res=0;
    for(int i=1;i<=k;i++)res+=dp[m][i];
    printf("%d\n",res);
    return 0;
} 
最后修改:2020 年 08 月 17 日 08 : 09 PM