没有合适的资源?快使用搜索试试~ 我知道了~
首页动态规划算法(下).ppt
动态规划算法(下).ppt
需积分: 42 18 下载量 192 浏览量
更新于2023-03-16
评论 1
收藏 2.1MB PPT 举报
动态规划算法(下).ppt动态规划算法(下).ppt动态规划算法(下).ppt
资源详情
资源评论
资源推荐
0-1 背包问题
给定 n 种物品和一背包。物品 i 的重量是 w
i
,其价值为 v
i
,背
包的容量为 C 。问应如何选择装入背包的物品,使得装入背包
中物品的总价值最大 ?
1
max
n
i i
i
v x
1
{0,1},1
n
i i
i
i
w x C
x i n
问题归结为寻找一个满足约束条件,并使目标函数达到最
大的解向量 X=(x
1
, x
2
, …, x
n
) 。
约束条件
目标函数
1. 最优子结构性质
设 (x
1
, x
2
, …, x
n
) 是所给 0/1 背包问题的一个最优解,
则 ( x
2
, …, x
n
) 是下面一个子问题的最优解:
1 1
2
{0,1} (2 )
n
i i
i
i
w x C w x
x i n
2
max
n
i i
i
v x
如若不然,设 (y
2
, …, y
n
) 是上述子问题的一个最优解,则
因此,
这说明 (x
1
, y
2
, …, y
n
) 是所给 0/1 背包问题比 (x
1
, x
2
, …, x
n
) 更优的
解,从而导致矛盾。
2 2
n n
i i i i
i i
v y v x
1 1
2
n
i i
i
w x w y C
1 1 1 1
2 2 1
n n n
i i i i i i
i i i
v x v y v x v x v x
2. 递归关系
设所给 0-1 背包问题的子问题
max
n
k k
k i
v x
{0,1},
n
k k
k i
k
w x j
x i k n
的最优值为 m(i , j) ,即 m(i , j) 是背包容量为 j ,可选择物品
为 i , i+1 ,…, n 时 0-1 背包问题的最优值。由 0-1 背包问题
的最优子结构性质,可以建立计算 m(i , j) 的递归式如下。
max{ ( 1, ), ( 1, ) }
( , )
0
( 1, )
i
i i
i
j w
m i j m i j w v
m i j
j w
m i j
( , )
0
0
n
n
n
j w
v
m n j
j w
3. 自底向上求解最优
值
void Knapsack(int *v,int *w,int c,int n,int **m)
{
int i,j,jmax;
jmax=min(w[n]-1,c);
for(j=0;j<=jmax;j++)
m[n][j]=0;
for(j=w[n];j<=c;j++)
m[n][j]=v[n];
for(i=n-1;i>1;i--)
{
jmax=min(w[i]-1,c);
for(j=0;j<=jmax;j++)
m[i][j]=m[i+1][j];
for(j=w[i];j<=c;j++)
m[i][j]=max(m[i+1][j],m[i+1][j-w[i]]+v[i]);
}
If(c<w[1])
m[1][c]=m[2][c];
else
m[1][c]=max(m[2][c],
m[2][c-w[1]]+v[1]);
}
时间复杂度: O(nc)
4. 构造最优解
void Traceback(int (**m,int *w,int c,int n,int *x)
{
int i;
for(i=1;i<n;i++)
{
if(m[i][c]==m[i+1][c])
x[i]=0;
else
{
x[i]=1;
c-=w[i];
}
}
x[n]=(m[n][c])?1:0;
}
时间复杂度: O(n)
剩余32页未读,继续阅读
huguifuture
- 粉丝: 34
- 资源: 12
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- ExcelVBA中的Range和Cells用法说明.pdf
- 基于单片机的电梯控制模型设计.doc
- 主成分分析和因子分析.pptx
- 共享笔记服务系统论文.doc
- 基于数据治理体系的数据中台实践分享.pptx
- 变压器的铭牌和额定值.pptx
- 计算机网络课程设计报告--用winsock设计Ping应用程序.doc
- 高电压技术课件:第03章 液体和固体介质的电气特性.pdf
- Oracle商务智能精华介绍.pptx
- 基于单片机的输液滴速控制系统设计文档.doc
- dw考试题 5套.pdf
- 学生档案管理系统详细设计说明书.doc
- 操作系统PPT课件.pptx
- 智慧路边停车管理系统方案.pptx
- 【企业内控系列】企业内部控制之人力资源管理控制(17页).doc
- 温度传感器分类与特点.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0