题目描述--->p1858 多人背包
分析:
很明显,这题是背包问题的一种变形.
求解 次优解or第k优解.
表示刚开始有点懵,看题解也看不太懂.
又中途去补看了一下背包九讲
然后感觉有些理解,但还是不算太清楚.
所以自己思考了一下.(应该算是大致理解了意思.
来分享一下思路.
题解里都说是裸的此类问题,并没有给出解释。
(给出的解释也大多是背包九讲里的一些抽象定义
前置知识
首先根据01背包的递推式：(这里按照一维数组来讲)
(v[i]代表物品i的体积,w[i]代表物品i的价值).
\(f(j)\)=\(max\left(f(j),f(j-v[i])+w[i]\right)\)
很容易发现\(f(j)\)的大小只会与\(f(j)\)、\(f(j-v[i])+w[i]\)有关
所以我们设\(f[i][k]\)代表体积为i的时候,第k优解的值.
则从\(f[i][1]\)...\(f[i][k]\)一定是一个单调的序列.
\(f[i][1]\)为体积为i的时候的最优解
解析
很容易发现,我们需要记录用其他物品来填充背包是否能得到更优解.
因此我们需要记录一个变量c1表示体积为j的时候的第c1优解能否被更新.
再去记录一个变量c2表示体积为j-v[i]的时候的第c2优解.
这就好像我们用5填充了5,得到的价值为10.
而我们可以用2,3填充5,得到更大价值为18.
而我们的3又可以被1,2填充,而使得我们得到更大价值
如此往复,我们就可以一直更新体积为5的价值,来更新第几优解.
简单概括一下
我们可以用v[i]去填充j-v[i]的背包去得到体积为j的情况,并获得价值w[i].
同理j-v[i]也可以被其他物品填充而获得价值.
此时,如果我们使用的填充物不同,我们得到的价值就不同.
这是一个刷表的过程(或者叫推表?
为什么是正确的?
(这里引用一句话)
一个正确的状态转移方程的求解过程遍历了所有可用的策略，也就覆盖了问题的所有方案。
个人
我尝试输出了一下这个刷表的过程.
//我将初值赋成了自己的生日 qwq
这里给出一部分的解释↓
-20021003 -20021003
4 -20020999
12 -20020991
-20020991 -20020991
16 -20020987
-20020987 -20020987
20 -20020983
-20020983 -20020983
24 -20020979
32 -20020971
当前情况为我们枚举完样例中体积为2的情况得到的表格.(我们仅得到了第一优解
下面情况为我们枚举样例中体积为5的情况
(此时我们再度刷新了表格..
(now代表当前枚举到的j.)
now::10
-20021003 -20021003
4 -20020999
12 -20020991
-20020991 -20020991
16 -20020987
-20020987 -20020987
20 -20020983
-20020983 -20020983
24 -20020979
32 22
此时我们枚举到了j=10,发现我们的f[10][1](即最优解)
大于用体积为5的物品去填充体积为5的背包.
且我们的f[10][2]小于他,那我们就可以得到我们的体积为10的次优解.
(因题目要求我们去求到前2优解的和,所以只考虑到第二列.
now::9
-20021003 -20021003
4 -20020999
12 -20020991
-20020991 -20020991
16 -20020987
-20020987 -20020987
20 -20020983
-20020983 -20020983
24 -20020979
32 22
这个时候我们发现无法更新f[9][1].(这个不能更新是指不能得到正的价值.
我们不能填充体积为4的背包来得到一个正的最优解(体积为4的背包价值也为负
now::8
-20021003 -20021003
4 -20020999
12 -20020991
-20020991 -20020991
16 -20020987
-20020987 -20020987
20 -20020983
18 -20020983
24 -20020979
32 22
此时我们发现可以更新f[8][1].
即对于体积为3的,我们再去用体积为5的物品填充,发现可以得到正的价值.
所以我们可以去更新f[8][1]，
然后尝试继续更新f[8][2].
因为我们的f[8]整整一列都是负数.(除了刚刚更新的f[8][1]
而我们现在可以使用体积为5的物品填充体积为3的背包得到体积为8的背包.
所以我们去检查是否存在f[3][2]能继续更新我们的f[8][2].
很不幸,我们枚举之后,发现并不能更新.-->f[8][2]不变.
now::7
-20021003 -20021003
4 -20020999
12 -20020991
-20020991 -20020991
16 -20020987
-20020987 -20020987
20 10
18 -20020983
24 -20020979
32 22
同上面解释,此时体积为7的背包可以被体积为2的填充,
通过比较发现填充得到的价值,不如之前得到的价值.
所以我们去更新f[7][2].
now::6
-20021003 -20021003
4 -20020999
12 -20020991
-20020991 -20020991
16 -20020987
-20020987 -20020987
20 10
18 -20020983
24 -20020979
32 22
没有体积为1的,所以无法更新f[6][1]与f[6][2]
now::5
-20021003 -20021003
4 -20020999
12 -20020991
-20020991 -20020991
16 6
-20020987 -20020987
20 10
18 -20020983
24 -20020979
32 22
可以直接填充空背包(体积为0)得到体积为5的情况.
此时通过比较发现直接填充所得到的价值为次优解.
所以更新f[5][2]
希望大家更好地理解一下这个求 次优解and第k优解 的过程
---------------------代码(附输出中间表格)-------------------
#include<bits/stdc++.h>
#define IL inline
#define RI register int
using namespace std;
IL void in(int &x)
{
int f=1;x=0;char s=getchar();
while(s>'9' or s<'0'){if(s=='-')f=-1;s=getchar();}
while(s>='0' and s<='9'){x=x*10+s-'0';s=getchar();}
x*=f;
}
int k,v,n,ans,cnt,now[55];
int V[288],W[288],f[5008][55];
int main()
{
//freopen("data.out","w",stdout);
//尝试输出中间变量我用了notepad,因为太长了啊! 辅助用
in(k),in(v),in(n);
for(RI i=0;i<=5000;i++)
for(RI j=0;j<=50;j++)f[i][j]=-20021003;//赋初值为-inf
f[0][1]=0;//体积为0的最优解为0.
for(RI i=1;i<=n;i++)
in(V[i]),in(W[i]);//V[i]为体积,W[i]为价值.
for(RI i=1;i<=n;i++)
for(RI j=v;j>=V[i];j--)
{
int c1=1,c2=1,cnt=0;
while(cnt<=k)
{
if(f[j][c1]>f[j-V[i]][c2]+W[i])
now[++cnt]=f[j][c1++];
else now[++cnt]=f[j-V[i]][c2++]+W[i];
}
//这里我选择了开数组记录当前得到的优解的值,在下面直接赋值给f[j]即可。
//可以试试手推,这个now数组会是单调递减的.
for(RI c=1;c<=k;c++)f[j][c]=now[c];
// printf("now::%d\n",j);
// for(RI w=1;w<=v;w++,puts(""))
// for(RI c=1;c<=k;c++)printf("%d\t",f[w][c]);
// puts("");//上面四行是输出中间变量的
}
for(RI i=1;i<=k;i++)ans+=f[v][i];
// for(RI w=1;w<=v;w++,puts(""))
// for(RI c=1;c<=k;c++)printf("%d ",f[w][c]);
printf("%d",ans);
}