华师一附中OI组

标题: 背包问题由浅入深 [打印本页]

作者: admin 时间: 2018-9-8 22:08
标题: 背包问题由浅入深
背包问题是一类物品选择问题，通常是求在一定条件下选择某些不同属性的物品以获得最大的评价值。典型题目如下：
1、1克，3克，4克，7克，8克的砝码各1个，能不能凑成10克的重量？
2、1克，3克，4克，7克，8克的砝码各4个，能不能凑成10克的重量？
3、1克，3克，4克，7克，8克的砝码无穷个，4个砝码以内能不能凑成10克的重量？
4、1克，3克，4克，7克，8克的金块各1个，价值分别是10元，25元，35元，80元，100元，不超过10克重量的情况下价值最大是多少元？
5、1克，3克，4克，7克，8克的金块各10个，价值分别是10元，25元，35元，80元，100元，不超过10克重量的情况下价值最大是多少元？
6、1克，3克，4克，7克，8克的金块各1个，价值分别是10元，25元，35元，80元，100元，恰好重量为10克的情况下价值最大是多少元？
7、1克，3克，4克，7克，8克的金块各1个，价值分别是10元，25元，35元，80元，100元，体积分别是1立方厘米，2立方厘米，3立方厘米，5立方厘米，6立方厘米，重量不超过10克，体积不超过10立方厘米的情况下价值最大是多少元？（似乎有点违背物理常识）
8、1克，3克，4克，7克，8克的金块各1个，价值分别是10元，25元，35元，80元，100元，凑到10克以上的重量至少需要多少钱？
9、1克，3克，4克，7克，8克的金块各1个，价值分别是10元，25元，35元，80元，100元，奇数克的砝码（1,3,7）至多选1个，不超过10克重量的情况下价值最大是多少元？
===

作者: admin 时间: 2018-9-9 17:36
第一题：1克，3克，4克，7克，8克的砝码各1个，能不能凑成10克的重量？
显然最朴素的做法就是枚举五种砝码，选或者不选，看看能不能凑成10克，朴素的代码如下：

#include <iostream>
using namespace std;
int a[]= {0,1,3,4,7,8}; ///砝码的重量
int a1,a2,a3,a4,a5;///记录是否被选
int x;
bool bb;
int main()
{
cin>>x;
bb=0;
for (a1=0; a1<=1; a1++)
for (a2=0; a2<=1; a2++)
for (a3=0; a3<=1; a3++)
for (a4=0; a4<=1; a4++)
for (a5=0; a5<=1; a5++) ///五种循环穷举
if (a1*a[1]+a2*a[2]+a3*a[3]+a4*a[4]+a5*a[5]==x)
{
bb=1;
cout<<a1<<a2<<a3<<a4<<a5<<endl; ///输出可选方案
}
if (bb) cout<<'Y';
else cout<<'N';
return 0;
}

复制代码

但这么做程序代码不可控，运行效率也很差。想想要是10个砝码怎么办？那不是要写10个循环，n个砝码呢？当然有人说用dfs写x选y的程序，那是另外一个做法，但是效率依然不高。
我们采用DP列表法来做此题，用fij表示前i个砝码能否凑出j这个重量，那么显然
f00=1 不用砝码也可以得到0克
fij=fi-1jh或者f(i-1)(j-ai) 前面不选ai能否得到j 后面是选择ai那么前面i-1个需要凑成j-ai克的重量，在电子表格中画个表看看这个迭代的过程。
于是编程如下：

#include <iostream>
using namespace std;
int a[]= {0,1,3,4,7,8};
bool f[6][30];///f[i][j]表示前面i个砝码能否凑成j克的重量
int x,r,c;
bool t1,t2;
int main()
{
cin>>x;
f[0][0]=1;
for (r=1; r<=5; r++)
for (c=0; c<=20; c++)
{
t1=f[r-1][c]; ///不用此砝码
if (c>=a[r]) t2=f[r-1][c-a[r]]; ///用此砝码，那么要保证c-a[r]>=0
else t2=0;
f[r][c]=t1||t2; ///或者操作，有一个满足就行
}
for (r=0; r<=5; r++) ///输出表格检查
{
for (c=0; c<=20; c++) cout<<f[r][c]<<' ';
cout<<endl;
}
if (f[5][x]) cout<<'Y';
else cout<<'N';
return 0;
}

复制代码

有同学很快的发现，类似杨辉三角，这个二维数组可以写成一维的，这个对于初学者，我们就不强求了。

作者: admin 时间: 2018-9-10 19:05
第二题，砝码的个数不是1个而是多个，有个笨笨的办法就是变成20个砝码来做这个题，11113333444477778888这样20个砝码，也可以在选择砝码的时候加上一个循环，枚举砝码被选择的次数，然后对结果进行||运算

#include <iostream>
using namespace std;
int a[]= {0,1,3,4,7,8};
int b[]= {0,4,4,4,4,4};
bool f[6][30];///f[i][j]表示前面i个砝码能否凑成j克的重量
int x,r,c,k;
bool t1,t2;
int main()
{
cin>>x;
f[0][0]=1;
for (r=1; r<=5; r++)
for (c=0; c<=20; c++)
{
t1=0;///记录初始值
for (k=0; k<=b[r]; k++) ///枚举可能的情况
{
if (k*a[r]<=c) t2=f[r-1][c-k*a[r]];///若能装下
t1=t1||t2; ///或者！！！！
}
f[r][c]=t1;
}
for (r=0; r<=5; r++) ///输出表格检查
{
for (c=0; c<=20; c++) cout<<f[r][c]<<' ';
cout<<endl;
}
if (f[5][x]) cout<<'Y';
else cout<<'N';
return 0;
}

复制代码

作者: admin 时间: 2018-9-10 19:06
第三题，限定砝码总个数最多4个，所以我们在记录这个重量能不能被凑出来的时候就应该记录所用的最少砝码数而不是简单的记录是都被凑出来。就以1 3 4 7 8 为例，f(3,4)是前3个砝码凑出重量4的最少砝码数量，应该是1。所以每次枚举最少砝码数，取其中的最小值。为了清晰和简便，凑不出来不用0表示，而用一个很大的数字，比如999代替。

#include <iostream>
#include <iomanip>
using namespace std;
int a[]= {0,1,3,4,7,8};
int b[]= {0,4,4,4,4,4};
int f[6][30];///f[i][j]表示前面i个砝码最少需要几个凑成j克的重量
int x,r,c,k;
int t1,t2;
int main()
{
cin>>x;
for (r=0; r<=5; r++)
for (c=0; c<=29; c++) f[r][c]=999;
f[0][0]=0;
for (r=1; r<=5; r++)
for (c=0; c<=20; c++)
{
t1=999;///记录初始值
for (k=0; k<=b[r]; k++) ///枚举可能的情况
{
if (k*a[r]<=c) t2=f[r-1][c-k*a[r]]+k;///若能装下
t1=min(t1,t2);
}
f[r][c]=t1;
}
for (r=0; r<=5; r++) ///输出表格检查
{
for (c=0; c<=20; c++) cout<<setw(4)<<f[r][c]<<' ';
cout<<endl;
}
if (f[5][x]) cout<<'Y';
else cout<<'N';
return 0;
}

复制代码

作者: admin 时间: 2018-9-19 10:14
第四题，这是我们传统意义上的基本背包问题，给定n个物品，每个物品有重量和价值，求最大重量一定情况下的价值。
我们仿照上面的例子，还是用f(i,j)表示前面i个物品能够凑成的，重量不超过j的时候价值的最大值。
那么应该可以想得到 f(i,j)=f(i-1,j)（不选第i个物品）或者 f(i-1, j-wi)+vj （选择第i个物品，这个时候要注意j>=wi）
初始值f(0,0)=0也是显然的。于是程序如下：

///标准背包
#include <iostream>
#include <iomanip>
using namespace std;
int w[]= {0,1,3,4,7,8};
int v[]= {0,10,25,35,80,100};
int f[6][200];///f[i][j]表示前面i个砝码在不超过j克的重量的情况下的最大价值
int x,r,c,k;
int t1,t2;
int main()
{
for (r=0; r<=5; r++)
for (c=0; c<=199; c++) f[r][c]=0;
for (r=1; r<=5; r++)
for (c=0; c<=20; c++)
{
t1=f[r-1][c];
if (w[r]<=c) t2=f[r-1][c-w[r]]+v[r];///若能装下
else t2=0;
f[r][c]=max(t1,t2);
}
for (r=0; r<=5; r++) ///输出表格检查
{
for (c=0; c<=20; c++) cout<<setw(4)<<f[r][c]<<' ';
cout<<endl;
}
return 0;
}

复制代码

作者: admin 时间: 2018-9-19 10:51
第五题，仿照第二题，加一维，枚举每个砝码的个数，参考代码如下

作者: admin 时间: 2018-9-19 13:18
以上都是简单的背包问题，我们用的填表大法，二维数组比较直观，但是有点浪费，其实也可以一维数组，那么就是本地迭代。在此之前，请认真体会fibo数列，辗转相除求最大公约数，杨辉三角的一维数组做法。

请看第一题，1,3,4,7,8的砝码各一个，能不能拼出10克的重量，我们用一维数组bi表示i克能否拼出，那么初始的时候，全部是0.
b0=1，
先来一个1克的砝码b1=1
再来一个3克的因为b0=b1=1，所以b(0+3)=b(1+3)=1
再来一个4克的。因为b0=b1=b3=b4=1所以 b(0+4)=b(1+4)=b(3+4)=b(4+4)=1
**
就是说从每来一个砝码，就把这个所有的为1的重量的加上这个砝码的重量设为1为了避免重复累加，应该类似杨辉三角，从后往前推。（！！！！！）
代码如下：

#include <iostream>
using namespace std;
int a[]= {0,1,3,4,7,8};
bool f[30];///表示能否凑出
int x,i,j;
int main()
{
f[0]=1;
for (i=1; i<=5; i++) ///枚举5个砝码
{
for(j=29; j>=a[i]; j--) ///由后向前
f[j]=f[j]||f[j-a[i]]; ///或者我可以，或者j-a[i]可以
}
for(j=0; j<=29; j++) cout<<f[j]<<' ';
return 0;
}

复制代码

第四题是标准的背包问题，用一维数组的解法如下，和前面有点不同的地方是这个判断标准，上面用的是或者运算，这里用的是求最大值的运算

#include <iostream>
using namespace std;
int w[]= {0,1,3,4,7,8};
int v[]= {0,10,25,35,80,100};
int f[30];
int x,i,j;
bool t1,t2;
int main()
{
for (i=1; i<=5; i++) ///枚举5个砝码
{
for(j=29; j>=w[i]; j--) ///由后向前
f[j]=max(f[j],f[j-w[i]]+v[i]); ///或者我可以，或者j-a[i]可以
}
for(j=0; j<=29; j++) cout<<f[j]<<' ';
return 0;
}

复制代码

作者: admin 时间: 2018-10-2 09:43
第一阶段总结：
1、简单背包问题就是填那个二维的表格，行对应每个物品的重量，列对应背包的容量重量，里面的元素看情况不同，也许是01表示此重量可否凑出，也许是可以凑出此重量的最小物品个数，或者是不超过此重量的最大价值。
2、标准是用二重循环，但是注意行列的顺序，外层循环枚举循环物品，里层循环枚举重量列表；
3、也可以用一维数组，但是注意要从后向前，
4、初始值有的时候是0，有的时候是999，有的时候是-999，想想为什么？

作者: admin 时间: 2018-10-2 19:47
训练题2：
P1510  精卫填海 http://hsyit.cn/forum.php?mod=viewthread&tid=36159
P1853  总分 Score Inflation http://hsyit.cn/forum.php?mod=viewthread&tid=36400
P2722  投资的最大效益  http://hsyit.cn/forum.php?mod=viewthread&tid=36398
P1802 5倍经验日 http://hsyit.cn/forum.php?mod=viewthread&tid=36413
P2925 [USACO08DEC]干草出售  http://hsyit.cn/forum.php?mod=viewthread&tid=36414

作者: admin 时间: 2018-10-14 10:49
综合练习：P1502  NASA的食物计划  http://hsyit.cn/forum.php?mod=viewthread&tid=36360
P1759 通天之潜水  http://hsyit.cn/forum.php?mod=viewthread&tid=36014
P1757 通天之分组背包  http://hsyit.cn/forum.php?mod=viewthread&tid=36148
P1417 烹调方案  http://hsyit.cn/forum.php?mod=viewthread&tid=36402
P1794 装备运输  http://hsyit.cn/forum.php?mod=viewthread&tid=36146
P1509 找啊找啊找GF http://hsyit.cn/forum.php?mod=viewthread&tid=36134

作者: admin 时间: 2019-7-8 15:27
一般的背包是在重量限定的情况下求价值的最大，但是也可以变形为价值限定的情况下求重量最小，比如潜水员问题：
给定N个氧气瓶，都有一定的重量和氧气容量，问需要X升氧气的情况下最少需要带多少重量。
这个题的推理和上面有相似之处，大家试着做做看。

作者: admin 时间: 2019-7-9 10:15
背包问题还有两个变形，多重背包和分组背包

欢迎光临华师一附中OI组 (http://hsyit.cn/)