南京大学厦门大学ACM百练算法设计与分析OpenJudge第六章习题解答.docx

南京大学厦门大学ACM百练算法设计与分析OpenJudge第六章习题解答.docx

《南京大学厦门大学ACM百练算法设计与分析OpenJudge第六章习题解答.docx》由会员分享，可在线阅读，更多相关《南京大学厦门大学ACM百练算法设计与分析OpenJudge第六章习题解答.docx（16页珍藏版）》请在冰点文库上搜索。

南京大学厦门大学ACM百练算法设计与分析OpenJudge第六章习题解答

第6章课后作业结题报告

第一题：

给定n种物品和一个背包，物品i（1≤i≤n）的重量是wi，其价值为vi，背包的容量为C，对每种物品只有两种选择：

装入背包或者不装入背包。

如何选择装入背包的物品，使得装入背包中物品的总价值最大？

这是一道老生常谈的背包问题，属于入门dp（DynamicProgramming动态规划）,

首先给出状态转移方程，设dp[i][j]表示用大小为j的背包去装前i个所能获得的最大价值,w[i]表示第i个物品的体积，v[i]表示第i个物品的价值。

关于第i个物品的决策，就是间单的”取与不取”，我们很容易得到如下的状态转移方程:

dp[i][j]=max（dp[i-1][j],dp[i-1][j-w[i]]+v[i]）;

这边dp[i-1][j]表示第i个物品不取，dp[i-1][j-w[i]]+v[i]表示第i个物品取

因为每次推导只用的到i-1维，我们其实可以只用一维的滚动数组就可以来求解。

这时候要逆序求解，这边不多做介绍

接下来是打印路径问题，这个需要逆序贪心打印。

第i个背包是否选取应该用dp[i][V]与dp[i-1][V]来比较，从而求解，dp[i][V]>dp[i-1][V]，V表示当前可存在的最大容量。

根据贪心，容量V越大价值同样装前i个一定更优，后面的推导的正解一定是基于dp[i][V]的，所以可以这么选

标程如下：

#include

#include

usingnamespacestd;

intdp[110][1010];

intn,c,ans[110];

intw[110],v[110];

voidprint（）{

inti,j,k;

k=c;

for（i=n;i>=1;i--）{

if（dp[i][k]!

=dp[i-1][k]）{

ans[i]=1;

k=k-w[i];

}

else{

}

}

return;

}

intmain（）{

inti,j,k;

scanf（"%d%d",&n,&c）;

for（i=1;i<=n;i++）{

scanf（"%d%d",&w[i],&v[i]）;

}

for（i=1;i<=n;i++）{

for（j=1;j<=c;j++）{

dp[i][j]=dp[i-1][j];

if（j>=w[i]）{

dp[i][j]=max（dp[i-1][j-w[i]]+v[i],dp[i][j]）;

}

}

}

printf（"%d\n",dp[n][c]）;

print（）;

for（i=1;i<=n;i++）{

printf（"%d\n",ans[i]）;

}

return0;

}

第二题：

设有n种不同面值的硬币，各硬币的面值存于数组T[1:

n]中。

现要用这些面值的硬币来找钱。

可以使用的各种面值的硬币个数存于数组Coins[1:

n]中。

对任意钱数0≤m≤20001，设计一个用最少硬币找钱m的方法。

对于给定的1≤n≤10，硬币面值数组T和可以使用的各种面值的硬币个数数组

Coins，以及钱数m，0≤m≤20001，计算找钱m的最少硬币数。

这一题属于背包问题的变形

这首先转化为背包问题，如下:

如输入数据:

13

23

53

其实可以转化为:

体积分别为:

111222555,

价值都为1的物品，问题转化成问你物体的体积总和恰好为m时需要最小的价值数，

dp[i][j]表示前i个物品中抽取任意个恰好为m，所耗费的最少价值数

dp[i][j]=min（dp[i-1][j],dp[i-1][j-w[i]]+1）;

但这边代码书写的时候要注意不是每个dp[i][j]的值都是可达到的，

即时任意一个数，不是你想凑就能凑出来的，所以这边要特判一下，先初始化为

足够大，如2000000000，然后在状态转移的时候都要先判断，子问题是否已经被求解。

标程如下:

#include

#include

usingnamespacestd;

intw[110],v[110];

intdp[110][20010];

intn,m;

voidinit（）{

for（inti=0;i<110;i++）{

for（intj=0;j<20010;j++）{

dp[i][j]=2000000000;

}

}

}

intmain（）{

inti,j,k;

intt,x,cnt=1;

scanf（"%d",&n）;

for（i=1;i<=n;i++）{

scanf（"%d%d",&t,&x）;

for（j=1;j<=x;j++）{

w[cnt]=t;

v[cnt]=1;

cnt++;

}

}

scanf（"%d",&m）;

init（）;

for（i=0;i

//cnt++;

dp[i][0]=0;

}

for（i=1;i

for（j=1;j<=m;j++）{

dp[i][j]=dp[i-1][j];

if（j>=w[i]&&dp[i-1][j-w[i]]!

=2000000000）{

dp[i][j]=min（dp[i][j],dp[i-1][j-w[i]]+1）;

}

}

}

if（dp[cnt-1][m]==2000000000）

printf（"-1"）;

else

printf（"%d",dp[cnt-1][m]）;

return0;

}

第三题：

给定n个矩阵{A1,A2,...,An}，考察这n个矩阵的连乘积A1A2...An。

由于矩阵乘法满足结合律，故计算矩阵的连乘积可以有许多不同的计算次序，这种计算次序可以用加括号的方式来确定。

矩阵连乘积的计算次序与其计算量有密切关系。

例如，考察计算3个矩阵{A1,A2,A3}连乘积的例子。

设这3个矩阵的维数分别为10*100，100*5，和5*50。

若按（A1A2）A3计算，3个矩阵连乘积需要的数乘次数为10*100*5+10*5*50=7500。

若按A1（A2A3）计算，则总共需要100*5*50+10*100*50=75000次数乘。

现在你的任务是对于一个确定的矩阵连乘方案，计算其需要的数乘次数。

这个首先他的运算顺序已经确定了，其实就是表达式求值，只不过把平时的表达式求值的数字换成矩阵而已。

很明显这涉及到优先级的选择，出现括号，必须考虑用栈来解决

思路这样的，例如样例中输入数据要求值的exp:

A（BC）

可以转化成exp：

”A*（B*C）=”

是的，你得把他换成标准的表达式，然后就是朴素的套用表达式求值的一般方法。

表达式求值的一般方法就是你必须设立符号栈，和操作数栈，必须设置符号的优先级顺序。

标程如下:

#include

#include

#include

#include

#include

#include

usingnamespacestd;

intn,ans;

stringexp,str;

intx,y;

structnode{

intx,y;

};

nodes[200];

intflage;

stackope;

stackv;

stringchange（stringt）{

intlength=t.length（）;

stringdes="";

for（inti=0;i

if（isalpha（t[i]））{

if（t[i+1]=='）'）{

des=des+t[i];

}

else{

des=des+t[i]+'*';

}

}

elseif（t[i]=='（'）{

des=des+t[i];

}

else{

if（t[i+1]=='）'）{

des=des+t[i];

}

else{

des=des+t[i]+'*';

}

}

}

des=des+t[length-1]+'=';

returndes;

}

nodecalc（nodea,nodeb）{

if（a.y!

=b.x）{

flage=1;

}

nodet;

ans=ans+a.x*a.y*b.y;

t.x=a.x;t.y=b.y;

returnt;

}

charcompare（chari,charj）{

if（i=='='）{

if（j!

='='）{

return'<';

}

else{

return'=';

}

}

if（i=='（'）{

if（j=='）'）{

return'=';

}

else{

return'<';

}

}

if（i=='*'）{

if（j=='（'）{

return'<';

}

else{

return'>';

}

}

}

intmain（）{

inti,j,k;

stringe;

while（cin>>n）{

for（i=1;i<=n;i++）{

cin>>str>>x>>y;

s[str[0]].x=x;

s[str[0]].y=y;

}

cin>>e;

flage=0;

ans=0;

exp=change（e）;

while（!

ope.empty（））{

ope.pop（）;

}

while（!

v.empty（））{

v.pop（）;

}

ope.push（'='）;

intl=exp.length（）;

for（k=0;k<=l-1;）{

if（isalpha（exp[k]））{

v.push（s[exp[k]]）;

k++;

}

else{

if（compare（ope.top（）,exp[k]）=='='）{

ope.pop（）;

k++;

}

elseif（compare（ope.top（）,exp[k]）=='<'）{

ope.push（exp[k]）;

k++;

}

else{

nodea=v.top（）;

v.pop（）;

nodeb=v.top（）;

v.pop（）;

v.push（calc（b,a））;

ope.pop（）;

}

}

}

if（!

flage）

cout<

else

cout<<"error"<

}

return0;

}

第四题:

一个多边形，开始有n个顶点。

每个顶点被赋予一个正整数值，每条边被赋予一个运算符“+”或“*”。

所有边依次用整数从1到n编号。

现在来玩一个游戏，该游戏共有n步：

第1步，选择一条边，将其删除

随后n-1步，每一步都按以下方式操作：

（1）选择一条边E以及由E连接着的2个顶点v1和v2；

（2）用一个新的顶点取代边E以及由E连接着的2个顶点v1和v2，将顶点v1和v2的整数值通过边E上的运算得到的结果值赋给新顶点。

最后，所有边都被删除，只剩一个顶点，游戏结束。

游戏得分就是所剩顶点上的整数值。

那么这个整数值最大为多少？

这是标准的区间dp问题，首先我们来一遍预处理，例如考虑输入数据中的

4553

我们可以转化成:

45534553

就是按原序列延长，变成之前序列的两倍，你会发现任何环形都可以用本区间上

的某一段来表示，这就可以把曲线化成直线，然后dp[i][j]表示区间[i,j]上

的最大值,dpmin[i][j]表示区间[i,j]上的最小值，可以发现:

dp[i][j]=max（dp[i][j],dp[i][k]+或*dp[k+1][j]）

=max（dp[i][j],dp[i][k]+或*dpmin[k+1][j]）

=max（dp[i][j],dpmin[i][k]+或*dpmin[k+1][j]）

=max（dp[i][j],dpmin[i][k]+或*dp[k+1][j]）

其中k>=i&&k

我们可以发现他本质的思想是小区间推出大区间。

标程如下:

#include

#include

#include

#include

usingnamespacestd;

typedeflonglongintll;

constllinf=20000000000000;

intn;

strings;

charop[110][110];

lldp[110][110],dpmin[110][110];

lla[110];

llcalc（lla,llb,charch）{

if（ch=='*'）{

returna*b;

}

elseif（ch=='+'）{

returna+b;

}

else{

return0;

}

}

intmain（）{

inti,j,k,t;

cin>>n;

for（i=1;i<=n;i++）{

cin>>t;

a[i]=t;

cin>>s;

op[i][i+1]=s[0];

}

for（i=n+1;i<=2*n;i++）{

a[i]=a[i-n];

}

//for（i=1;i<=2*n;i++）{

//printf（"%d",a[i]）;

//}

//printf（"\n"）;

for（i=n+1;i<2*n;i++）{

op[i][i+1]=op[i-n][i+1-n];

}

//for（i=1;i<2*n;i++）{

//printf（"%c",op[i][i+1]）;

//}

//printf（"\n"）;

for（i=1;i<=2*n;i++）{//初始化为最小值

for（j=i;j<=2*n;j++）{

dp[i][j]=-inf;

dpmin[i][j]=inf;

}

}

for（i=1;i<=2*n;i++）{

dp[i][i]=a[i];

dpmin[i][i]=a[i];

}

for（i=1;i<2*n;i++）{

dp[i][i+1]=calc（a[i],a[i+1],op[i][i+1]）;

dpmin[i][i+1]=calc（a[i],a[i+1],op[i][i+1]）;

}

for（i=3;i<=n;i++）{

for（j=1;j+i-1<=2*n;j++）{

for（k=j;k

dp[j][i+j-1]=max（dp[j][i+j-1],calc（dp[j][k],dp[k+1][i+j-1],op[k][k+1]））;

dp[j][i+j-1]=max（dp[j][i+j-1],calc（dp[j][k],dpmin[k+1][i+j-1],op[k][k+1]））;

dp[j][i+j-1]=max（dp[j][i+j-1],calc（dpmin[j][k],dp[k+1][i+j-1],op[k][k+1]））;

dp[j][i+j-1]=max（dp[j][i+j-1],calc（dpmin[j][k],dpmin[k+1][i+j-1],op[k][k+1]））;

}

for（k=j;k

dpmin[j][i+j-1]=min（dpmin[j][i+j-1],calc（dp[j][k],dp[k+1][i+j-1],op[k][k+1]））;

dpmin[j][i+j-1]=min（dpmin[j][i+j-1],calc（dp[j][k],dpmin[k+1][i+j-1],op[k][k+1]））;

dpmin[j][i+j-1]=min（dpmin[j][i+j-1],calc（dpmin[j][k],dp[k+1][i+j-1],op[k][k+1]））;

dpmin[j][i+j-1]=min（dpmin[j][i+j-1],calc（dpmin[j][k],dpmin[k+1][i+j-1],op[k][k+1]））;

}

}

}

llans=-inf-10000000;

for（i=1;i<=n;i++）{

if（dp[i][i+n-1]>ans）{

ans=dp[i][i+n-1];

}

}

cout<

return0;

}