tceic.com
学霸学习网 这下你爽了
赞助商链接
当前位置:首页 >> 学科竞赛 >>

01背包(信息学竞赛)


信息学奥林匹克竞赛
——01背包

01背包是在M件物品取出若干件放在空间为W的背包里,每 件物品的体积为W1,W2……Wn,与之相对应的价值为 P1,P2……Pn。求出获得最大价值的方案。

对于每一个物品来说,只有两种状态,放(1)和不放(0)。 故这种类型的题目统称01背包问题。 考虑用动态规划的方法来解决,这里的:
阶段是:在前N件物品中,选取若干件物品放入背包中; 状态是:在前N件物品中,选取若干件物品放入空间为W的背包 中的所能获得的最大价值; 决策是:第N件物品放或者不放; 由此可以写出动态转移方程。

我们用F[i,j]表示在前 i 件物品中选择若干件放在空间为 j 的背 包里所能获得的最大价值。 Wi为第i件物品的体积,Pi为第i件物品的价值。 则动态转移方程为: F[i][j] = max{ F[i-1][j-Wi] + Pi (j>=Wi), F[i-1][j] }
例如:第i个物品的空间w[i]=5, 价值p[i]=10。
假如前i-1个物品填满空间5,所获得的最大价值为10。 假如前i-1个物品填满空间10,所获得做大价值为15。 if(选第i个物品) F[i][10] =F[i-1][5] + 10=20

if(不选第i个物品) F[i][10] =F[i-1][10]=15 那么F[i][10] =20。

1302: VIJOS-P1133 装箱问题
动归解法:其中不涉及到价值Pi,我们可以认为空间和价值相等。 所以其动态转移方程为: F[i,j] = max{ F[i-1,j-Wi]+Wi (j>=Wi), F[i-1,j] } #include<stdio.h> int n,w[31],f[31][20001],v; int max(int a,int b){return a>b?a:b;} int main() { int i,j; scanf("%d%d",&v,&n); for(i=1;i<=n;i++) scanf("%d",&w[i]); for(i=1;i<=n;i++) for(j=1;j<=v;j++) { f[i][j]=f[i-1][j]; if(j>=w[i]) f[i][j]=max(f[i-1][j-w[i]]+w[i],f[i][j]); } printf("%d",v-f[n][v]); return 0; }

#include<stdio.h> int f[20001]; int v,n,w; int main() { int i,j; scanf("%d%d",&v,&n); f[0]=1; for(i=1;i<=n;i++) { scanf("%d",&w); for(j=v;j>=w;j--) { if(f[j-w]==1) f[j]=1; } } j=v; while(f[j]==0) j--; printf("%d",v-j); return 0; }

空间优化!由二维压缩成了一维

寻找目标空间被填满时一定要从后向前找,避免重 复的添加。如果从前向后的话就会再次找到刚刚填 好的空间。
这也是01背包的代码的常规写法。

//循环n个物品

//循环找前i-1个物品的所有组合所能达到的空间 //如果空间j-w能够被前i-1个物品的一个组合填满 //那么填加上第i个物品后就能填满空间j

空间:0 F[]: 1

1

2

3

4

5

6

7

8

N=3 V=8 124

1277: VIJOS-P1104 采药
本题中采药品的时间可以认为是01背包 中物品的空间,药的价值认为是01背包 中物品的价值。 #include<stdio.h> int f[1001],n,ans,t; int main() { int i, j,a,b; scanf("%d%d",&t,&n); for(i=1;i<=n;i++) { scanf("%d%d",&a,&b); for(j=t;j>=a;j--) { if(f[j]<f[j-a]+b) f[j]=f[j-a]+b; } } printf("%d",f[t]); return 0; }

1424: VIJOS-P1317 开心的金明
#include<stdio.h> int n,s; int f[30001]; int main() { int i,j,a,b; scanf("%d%d",&s,&n); for(i=1;i<=n;i++) { scanf("%d%d",&a,&b); for(j=s;j>=a;j--) { if( f[j] < f[j-a] + a*b ) f[j]=f[j-a]+a*b; } } printf("%d",f[s]); return 0; }

1438: VIJOS-P1334 NASA的食物计划
#include <stdio.h> int v,m,n,f[401][401]; int main() { int i,j,k; int x,y,z; scanf("%d%d%d",&v,&m,&n); for(i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); for(j=v;j>=x;j--) for(k=m;k>=y;k--) { if(f[j][k]<f[j-x][k-y]+z) f[j][k]=f[j-x][k-y]+z; } } printf("%d",f[v][m]); return 0; }

动归解法: #include <stdio.h> int v,m,n,f[51][401][401]; int max(int a,int b) {return a>b?a:b;} int main() { int i,j,k; int x,y,z; scanf("%d%d%d",&v,&m,&n); for(i=1;i<=n;i++) { scanf("%d%d%d",&x,&y,&z); for(j=1;j<=v;j++) for(k=1;k<=m;k++) { f[i][j][k]=f[i-1][j][k]; if( j>=x && k>=y ) f[i][j][k]=max(f[i][j][k],f[i-1][j-x][k-y]+z); } } printf("%d",f[n][v][m]); }


赞助商链接
推荐相关:

信息学竞赛方法

信息学竞赛方法 - 信息学竞赛(NOIP)初赛、复赛学习方法推荐... (分析:背包问题) ⑥ 分治算法 ⑦ 搜索算法(fx:...信息学竞赛(NOIP)复赛学习方法推荐 二 01 确定...


合肥市第二十九届青少年信息学奥林匹克竞赛(小学组)试...

合肥 2012‐12‐01 第 1 页/共 3 页 “讯飞杯”合肥市第二十九届信息学奥林匹克竞赛 小学组 1.素数(number) 【问题描述】 期中考试刚刚结束,聪聪是班上...


2013年宁波市鄞州区信息学竞赛复赛试题(小学组)

2013年宁波市鄞州区信息学竞赛复赛试题(小学组)_学科竞赛_小学教育_教育专区。鄞州...接下来 n 行: i 行第(1≤? i? ≤? n) 中包含一个 01 串; 01 “...


信息学奥赛辅导C语言教程免费学习_C/C++_教学视频大全

针对中学阶段信息学奥林匹克竞赛进行相关的辅导,课程中涉及程序语言、算法以及竞赛...135***5962015-11-13 01:11:46 一个字好 二个字好好 三个字呢? 陆川暄...


NOIP信息学初赛模拟试题C++(1)

NOIP信息学初赛模拟试题C++(1)_学科竞赛_初中教育_...但每种物品的数量是无限的,同时有 一个背包,最大...给定一个 01 串,请你找出长度介于 a,b 之间,...


第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++...

第十九届2013全国青少年信息学奥林匹克联赛初赛试题C++及解析_学科竞赛_高中教育_...A.4 B.8 C.32 D.128 2.二进制数 11.01 在十进制下是()。 A.3.25...


背包九讲完整版 + hdu 代码

背包问题九讲 v1.0 目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲...更重要 的是:不大量思考,绝对不可能学好动态规划这一信息学奥赛中最精致的部分...


绝对经典背包九讲完整版

更重要的是:不大量思考,绝对不可能学好动态规划这一信息学奥赛中最精致的部分 背包问题九讲 v1.0 目录 第一讲 01 背包问题 第二讲 完全背包问题 第三讲 多...


信息学竞赛常用的算法思想讲座之五(贪婪算法)

信息学竞赛常用算法思想信息学竞赛常用算法思想隐藏>> 中华IT 学习网 www.100itx...最后,应用该算法给出 货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最...


信息学竞赛常用的算法思想讲座之四(回溯算法)

信息学竞赛常用算法思想信息学竞赛常用算法思想隐藏>> 中华IT 学习网 www.100itx...本章集中阐述回溯方法,这种方法被用来设计货箱装船、背包、最大完备子图、旅行...

网站首页 | 网站地图
All rights reserved Powered by 学霸学习网 www.tceic.com
copyright ©right 2010-2021。
文档资料库内容来自网络,如有侵犯请联系客服。zhit325@126.com