南京大学厦门大学ACM百练算法设计与分析OpenJudge第六章习题解答.docx
- 文档编号:9894325
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:16
- 大小:18.67KB
南京大学厦门大学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; stack stack 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; }
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 南京大学 厦门大学 ACM 算法 设计 分析 OpenJudge 第六 习题 解答
![提示](https://static.bingdoc.com/images/bang_tan.gif)