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


推荐相关:

部分贪心算法思想在信息学竞赛中的应用

部分贪心算法思想在信息学竞赛中的应用_工学_高等教育...这是一个很经典的背包问题,但由于背包容量很大,所以...文档贡献者 达流士一号一号 贡献于2011-07-01 ...


动态规划01背包问题

动态规划01背包问题_计算机软件及应用_IT/计算机_专业资料。信息学竞赛动态规划 0/1 背包问题【0/1 背包问题】 在 0/1 背包问题中,需对容量为 c 的背包进行...


部分贪心在信息学竞赛中的应用

wtswu95贡献于2011-01-15 0.0分 (0人评价)暂无...清华附中 高逸涵 部分贪心思想在信息学竞赛中的应用 ...这是一个很经典的背包问题, 但由于背包容量很大, ...


背包类型DP

信息学竞赛中,题目不会简单的给出 01 背包模型,需要我们从题意中勾画,设定某 些方案,从而变成经典的 01 背包模型。 【例题】采药 1049——0/1 背包 【问题...


4种常见的动态规划模型

(一)、背包模型 可用动态规划解决的背包问题,主要有 01 背包和完全背包。 对于...区间模型的动态规划, 在历届的信息学竞赛, 应用非常广泛, noi95 的石子合并...


如何学习动态规划

动态规划无 疑是其中一颗璀璨的明星,在信息学竞赛的舞台上绽放出夺目的光彩。IO...数轴动态规划类,题库:01 背包;装箱问题(noip01)。 树型动态规划类,题库:...


动态规划阶段总结之基础篇[必看]

动态规划阶段总结之基础篇 by Zc [序言]动态规划是信息学竞赛中最重要的知识点...当其背包的权值没有限制时是无法 1 我个人在感觉上觉得 01 背包这个模型其实...


NOIP普及组初赛模拟试题四

信息学竞赛普及组初赛模拟试题(四) 一、选择题: (...但每种物品的数量是无限的,同时有 一个背包,最大...; ③ ; ② ; 二、 【问题描述】给定一个 01 ...


Problem Set

背包问题 Problem5 任务调度 Problem6 果子合并 ...01 序列 Problem9 生日蛋糕 四、 图论算法 Problem...中华信息学竞赛网 www.100xinxi.com Problem4 十字...


浅谈数据的合理组织

不能被直 接购买.显然,如果题目中没有附件,那么本题即为标准的 01 背包问题...1 参见《算法艺术与信息学竞赛》贪食的九头龙中对算法复杂度的分析 我们是否有...

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