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


推荐相关:

01背包代码及分析

01背包代码及分析_信息与通信_工程科技_专业资料。01背包代码及分析,超级详细0/1 背包问题动态规划详解及 C 代码 背包问题动态规划详解及 动态规划详动态规划是用...


如何学习信息学奥赛免费学习_高中其他_教学视频大全

视频教程,幼狮精英学馆全套教学,在线学习高中其他课程,如何学习信息学奥赛视频下载... 第1章 本章的标题 01 了解信息学奥赛及如何学习和参赛 10分钟 评论(共8条)...


2013安徽省信息学竞赛试题(小学组)

2013安徽省信息学竞赛试题(小学组)_五年级其它课程_其它课程_小学教育_教育专区...文档贡献者 jiangwei_627 贡献于2016-01-24 相关文档推荐 暂无相关推荐文档 ...


01背包问题不同算法设计、分析与对比

01背包问题不同算法设计、分析与对比_机械/仪表_工程科技_专业资料。实践动态规划、贪心、回溯以及分支限界算法程序设计 实验三 01 背包问题不同算法设计、分析与...


2015年包河区青少年信息学(小学组)竞赛试题

2015年包河区青少年信息学(小学组)竞赛试题_学科竞赛_小学教育_教育专区。2015 ...题目是这样的: 给一个 M 行 N 列的 01 矩阵,让你选出一些行(不一定选出...


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

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


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

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


第13届2015少儿信息学竞赛笔试试题

第13届2015少儿信息学竞赛笔试试题_学科竞赛_小学教育_教育专区。第十三届绍兴市...文档贡献者 钱杲 贡献于2016-01-30 1/2 相关文档推荐 第13届2015绍兴少儿...


绝对经典背包九讲完整版

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


信息学奥林匹克竞赛试题(2)

信息学奥林匹克竞赛试题(2)_初一数学_数学_初中教育_教育专区。11信息...: 阅读程序并写出运行结果( +++=) 1.program test01; var x,y,s,p:...

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