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]); }


推荐相关:

信息学竞赛方法

(分析:背包问题) ⑥ 分治算法 ⑦ 搜索算法(fx:暴搜——枚举、打表、加剪枝...信息学竞赛(NOIP)复赛学习方法推荐 二 01 确定你的语言 NOIP 包括三种语言 c/...


01背包问题

01背包问题_信息与通信_工程科技_专业资料。01背包问题 01 背包问题 1、问题描述:给定 N 种物品和一个背包。物品 i 的重量是 Wi,其价值位 Vi ,背包的容量为...


信息学竞赛常用的算法思想讲座之一(动态规划)

信息学竞赛常用算法思想信息学竞赛常用算法思想隐藏>> 中华IT 学习网 www.100itx...4 节的 0 / 1 背包问题。如前所述,在该问题中需要决定 x1 .. xn 的值...


绝对经典背包九讲完整版

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


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

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


NOI信息学竞赛辅导免费学习_实战_教学视频大全

视频教程,糖果空中教室全套教学,在线学习实战课程,NOI信息学竞赛辅导视频下载... 课程概述 高中信息学竞赛辅导 适用人群 ...王纯洁2016-08-14 01:08:36 好 马来...


背包九讲完整版 + hdu 代码

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


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

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


多重背包问题

多重背包问题_电脑基础知识_IT/计算机_专业资料。NOIP 信息学 转自:背包问题九...转化为 01 背包问题 另一种好想好写的基本方法是转化为 01 背包求解:把第 i...


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

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

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