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 代码 背包问题动态规划详解及 动态规划详动态规划是用...


01背包问题

01 背包问题一、问题描述一个正在抢劫商店的小偷发现...计算机科学和经济学中使 用的,通过把原问题分解为...通常采用自底向上的方法; 4.利用计算的信息构造一...


背包类型DP

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


动态规划之01背包问题(最易理解的讲解)

动态规划之01背包问题(最易理解的讲解)_天文/地理_自然科学_专业资料。01 背包...一起来学广场舞 广场舞活动方案 社区广场舞策划方案 广场舞有益于身心健康...


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

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


01背包问题动态规划详解

01背包问题动态规划详解_计算机软件及应用_IT/计算机_专业资料。01背包问题动态规划详解 动态规划是用空间换时间的一种方法的抽象。其关键是发现子问题和记录其结 ...


01背包问题动态规划详解及C++代码

01背包问题动态规划详解及C++代码_计算机软件及应用_IT/计算机_专业资料。0/1 背包问题动态规划详解及 C++代码 1. 问题描述 给定一个载重量为 C 的背包? n 个...


01背包问题代码

01背包问题代码_理学_高等教育_教育专区。有关c语言程序背包代码算法设计与分析 实验报告—0/1 背包问题 - 【问题描述】 问题描述】 w v 种物品和一个背包。 ...


01背包问题论文

01背包问题论文_计算机软件及应用_IT/计算机_专业资料。01背包问题论文 ,贪心算法01 背包问题计科一班 刘东赫 2012020518 论文主要内容: 一、 问题描述 给定 n ...


01背包问题 分支界限法

01背包问题 分支界限法_计算机软件及应用_IT/计算机_专业资料。刚做完实验上交的...一起来学广场舞 广场舞活动方案 社区广场舞策划方案 广场舞有益于身心健康文档...

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