动态规划ppt.ppt

文档介绍：动态规划ppt
第1页，共50页，2022年，5月20日，15点16分，星期一
简介
动态规划简称DP，是在20世纪50年代由一位卓越的美国数学家Richcard Bellman发明的。它作为一种重要的工具在应用数学中被广泛的。
设d[i][j]为前i种硬币组成j元的方法数。
d[i][j] = d[i-1][j] + d[i-1][j-vi]
d[0][0]=1,d[0][1…S]=0
空间复杂度为O(n2),浪费！
第15页，共50页，2022年，5月20日，15点16分，星期一
d[0]=1; d[1…S]=0;
for (i=1; i<=n; i++)
{ for (j=S; j>=vi; j--)
{      d[j] += d[j-vi];  }}
第16页，共50页，2022年，5月20日，15点16分，星期一
0-1背包问题：
给定n种物品和一背包。物品i的重量是wi，其价值为vi，背包的容量为c。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大?
第17页，共50页，2022年，5月20日，15点16分，星期一
设m(i,j)是背包容量为j，可选择物品为i，i+1，…,n时，0-1背包问题的最优值。
m(i,j) = max{ m(i+1,j), m(i+1,j-wi)+vi} j>=wi
m(i+1,j) 0<=j<wi
m(n,j) = vn j>=wn
0 0<=j<wn
第18页，共50页，2022年，5月20日，15点16分，星期一
d[0…c]=0;
for (i=1; i<=n; i++)
{ for (j=c; j>=wi; j--)
{      d[j] = max(d[j],d[j-wi]+vi);  }}
第19页，共50页，2022年，5月20日，15点16分，星期一
推荐题目：
?id=1384 Piggy-Bank
第20页，共50页，2022年，5月20日，15点16分，星期一
硬币问题2：
有n种硬币，每种硬币的面值为vi元，有mi枚，问用这n种硬币找零S元的方法数。
第21页，共50页，2022年，5月20日，15点16分，星期一
d[0]=1;d[1…S]=0;
for (i=1; i<=n; i++)
{ for (j=S; j>=vi; j--)
{ for(k=1;k<=mi;k++)
{
      if (j-k*vi>=0) d[j] += d[j-k*vi];
}  }}
第22页，共50页，2022年，5月20日，15点16分，星期一
硬币问题3：
有n种硬币，每种硬币的面值为vi元，有无数枚，问用这n种硬币找零S元的方法数。
第23页，共50页，2022年，5月20日，15点16分，星期一
d[0]=1;d[1…S]=0;
for (i=1; i<=n; i++)
{ for (j=S; j>=vi; j--)
{ for(k=1;;k++)
{
      if (j-k*vi>=0) d[j] += d[j-k*vi];
else break;
}  }}
第24页，共50页，2022年，5月20日，15点16分，星期一
d[0]=1; d[1…S]=0;
for (i=1; i<=n; i++)
{ for (j=vi;j<=S; j++) //无数的时候是顺向
{      d[j] += d[j-vi];  }}
第25页，共50页，2022年，5月20日，15点16分，星期一
推荐题目：
?pid=1248 寒冰王座
?pid=1171 Big Event in HDU
第26页，共50页，2022年，5月20日，15点16分，星期一
?id=2614 Old Wine Into New Bottles
有n种小瓶子，每种瓶子容量范围是Vi1——Vi2，要灌满容量为L的大瓶子。问最少差多少体积没有灌满。
设d[i]表示体积为i是否可以达到。若v可取到，则
d[i]=d[i] || d[i-v]
第27页，共50页，2022年，5月20日，15点16分