您现在的位置:首页 > >

紫书第九章-----动态规划初步(DAG上的动态规划之硬币问题)

发布时间:

本文参考刘汝佳《算法竞赛入门经典》(第2版)*
动态规划的核心是状态和状态转移方程**


DAG上的动态规划一定要结合图来思考,要心中有图,或者在纸上画图,谨记!这样可以真正理解!求解状态转移方程的过程其实就是在填写一个表格!把表填好了,所有状态就填好了
硬币问题


【说明】
DAG上的动态规划问题!笔者“建立的图”都是从S到0。d(i)定义为以i开始到0结束的最长/短路。具体看下面代码及相关注释。
##记忆化搜索求解



/*
【本代码求解最少硬币】
状态确定:必须是从S状态到0状态(注意这里状态的含义),这些状态其实就是DAG上的点,每种面值就是边。
***注意下面代码建的图是从S到0建图的(从0到S建图也可以)。并且d(i)定义为从状态i到状态0的最短路,
当然也可以定义d(i)为从状态S到状态i的最短路(即以状态i结束的最短路)
S -> 0
1)求最多硬币(类似于最少硬币情况,只需改动本代码的三处,注释中已经标明)
d(i)表示从状态i到状态0的最长路
d(i)=max{d(j)+1 | (i,i-coin[j])∈E} ,(i,i-coin[j])∈E的意思就是i>=coin[j]

边界情况:d(0)=0
预处理:d(i)=-1,表示还没有访问过
初始化:d(i)=-INF,为了无解情况标记
无解:d(i)的最终结果是负数

2)求最少硬币(本代码解决该问题)
d(i)表示从状态i到状态0的最短路
d(i)=min{d(j)+1 | (i,i-coin[j])∈E},(i,i-coin[j])∈E的意思就是i>=coin[j]

边界情况:d(0)=0
预处理:d(i)=-1,表示还没有访问过
初始化:d(i)=INF,为了无解情况标记
无解:d(i)的最终结果是INF

*/

/*
求解动态规划的状态转移方程,可以使用递归+记忆化搜索,或者使用递推(填表法)。下面使用
这两种方法求解最小硬币数。(最大硬币数很类似,只需稍作改动,后面直接给出相应代码。)
*/

#include
#include

using namespace std;

const int maxn=1005;//假设硬币面值最大种类数
const int INF = (1<<30);

int coin[maxn];//各硬币面值
int d_min[maxn*maxn];//dp核心数组
int n;//硬币面值种类数
int S;//要得到的钱数
int path[maxn*2];//假设路径长度不超过2*maxn,用来记录路径
int solution[maxn][maxn];//假设最多的方案小于maxn
int solution_cnt;//方案数,全局变量自动初始化为0
int coin_cnt[maxn];//记录每种硬币数目,coin[1]表示第一种硬币数,以此类推

void init(){
cout<<"硬币面值种类总数:";
cin>>n;
cout<<"各面值:";
for(int i=1;i<=n;i++){
cin>>coin[i];
}
memset(d_min,-1,sizeof(d_min));
d_min[0]=0;
cout<<"要凑得的钱数:";
cin>>S;

}

int dp(int i){
int &ans=d_min[i];
if(ans!=-1) return ans;
ans=INF;//改成求最大硬币数时,把此处的INF改成-INF

for(int j=1;j<=n;j++){
if(i>=coin[j]){
//改成求最大硬币数时,把下面的一行改成:ans=max(ans,dp(i-coin[j])+1);
ans=min(ans,dp(i-coin[j])+1);
}
}
return ans;
}

void print_dp_path(int i){
for(int j=1;j<=n;j++){
if(i>=coin[j] && d_min[i]==d_min[i-coin[j]]+1){
cout< print_dp_path(i-coin[j]);
break;
}
}
}
//输出所有DAG图上的路径,并记录所有方案(去除重复)
void print_dp_all_path(int i,int cnt){
if(0==i){
//下面打印的仅仅是构造了DAG的边
cout<<">>";
for(int k=0;k cout< }
cout<
//下面去除重复,记录所有方案(每种方案对应各面值硬币的使用数目统计)
memset(coin_cnt,0,sizeof(coin_cnt));
for(int k=0;k coin_cnt[path[k]]++;
}

//判断之前的方案中是否已经存在和本方案相同的方案,若存在返回true
bool flag=false;//注意这里初始化是false,因为初始方案数solution_cnt=0
for(int k=1;k<=solution_cnt;k++){
flag=true;
for(int kk=1;kk<=n;kk++){
if(coin_cnt[kk]!=solution[k][kk]){
flag=false;
break;
}
}
if(flag) break;
}
if(!flag){
solution_cnt++;
for(int kk=1;kk<=n;kk++){
solution[solution_cnt][kk]=coin_cnt[kk];
}
}

}
for(int j=1;j<=n;j++){
//如果把d_min[i]==d_min[i-coin[j]]+1去掉,相当于dfs了
if(i>=coin[j] && d_min[i]==d_min[i-coin[j]]+1){
//注意这里不要用++cnt,因为++cnt会随着这个for循环不断进行++运算,比如
//i=10,coin依次有2,3,5,这将导致path[1]=1,path[2]=2,path[3]=3,而实际上
//他们都应该是path[1],不应该让++cnt
path[cnt]=j;
print_dp_all_path(i-coin[j],cnt+1);
}
}
}

int main()
{
init();
cout<<"**********************求解最小硬币数(递归+记忆化搜索)**********************"< int res=dp(S);
//改成求最大硬币数时,把res>=INF改成res<0
if(res>=INF){
cout<<"无解"< }else{
cout<<"最小硬币数:"< cout<<"最小字典序路径(面值):";
print_dp_path(S);
cout< cout<<"所有DAG图的路径-->"< print_dp_all_path(S,0);
cout<<"所有解决方案(每种面值硬币使用数目)-->"< for(int i=1;i<=solution_cnt;i++){
cout<<">>";
for(int j=1;j<=n;j++){
cout< }
cout< }
}
return 0;
}



##递推求解


#include
#include
using namespace std;

const int maxn=1005;
const int INF=(1<<30);

int coin[maxn];
int S;
int n;
int d_max[maxn*maxn];
int d_min[maxn*maxn];
int path_max[maxn];//记录最长路
int path_min[maxn];//记录最短路


void read(){
cout<<"硬币面值种类数:";
cin>>n;
cout<<"各面值是:";
for(int i=1;i<=n;i++){
cin>>coin[i];
}
cout<<"要凑得的钱数:";
cin>>S;
}

void dp(){
//初始化,如果最后需要的硬币数是个很大的数或很小的数,说明无解
for(int i=1;i<=S;i++){
d_max[i]=-INF;
d_min[i]=INF;
}
d_max[0]=d_min[0]=0;//从0状态到0状态的硬币数是0,这个很关键
for(int i=0;i<=S;i++){
for(int j=1;j<=n;j++){
if(i>=coin[j]){
if(d_max[i] d_max[i]=d_max[i-coin[j]]+1;
path_max[i]=j;//同时记录路径
}
if(d_min[i]>d_min[i-coin[j]]+1){
d_min[i]=d_min[i-coin[j]]+1;
path_min[i]=j;
}
}
}
}
}



void print_path_max(int i){
while(i){
cout< i-=coin[path_max[i]];
}
cout<}

void print_path_min(int i){
while(i){
cout< i-=coin[path_min[i]];
}
cout<}


int main()
{
cout<<"**************************求最多最少硬币(递推法)**************************"< read();
cout< dp();
cout<<"最大硬币数及最小字典序DAG路径(面值):";
cout< print_path_max(S);
cout<<"最小硬币数及最小字典序DAG路径(面值):";
cout< print_path_min(S);
return 0;
}



在上面递推法的基础上,改变状态定义,再次求解最大最小硬币数。现在笔者把d(i)定义为以S开始以i结束的最长/短路求解最大最小硬币数,状态转移方程变为:


d(i)=max{d(i+coin[j])+1 | i+coin[j]<=S}(最大硬币数)d(i)=min{d(i+coin[j])+1 | i+coin[j]<=S }(最小硬币数)

#include
#include
using namespace std;

const int maxn=1005;
const int INF=(1<<30);

int coin[maxn];
int S;
int n;
int d_max[maxn*maxn];
int d_min[maxn*maxn];
int path_max[maxn];//记录最长路
int path_min[maxn];//记录最短路


void read(){
cout<<"硬币面值种类数:";
cin>>n;
cout<<"各面值是:";
for(int i=1;i<=n;i++){
cin>>coin[i];
}
cout<<"要凑得的钱数:";
cin>>S;
}

void dp(){
//初始化,如果最后需要的硬币数是个很大的数或很小的数,说明无解
for(int i=0;i d_max[i]=-INF;
d_min[i]=INF;
}
d_max[S]=d_min[S]=0;//从0状态到0状态的硬币数是0,这个很关键
for(int i=S;i>=0;i--){
for(int j=1;j<=n;j++){
if(i+coin[j]<=S){
if(d_max[i] d_max[i]=d_max[i+coin[j]]+1;
path_max[i]=j;//同时记录路径
}
if(d_min[i]>d_min[i+coin[j]]+1){
d_min[i]=d_min[i+coin[j]]+1;
path_min[i]=j;
}
}
}
}
}



void print_path_max(int i){
while(i cout< i+=coin[path_max[i]];
}
cout<}

void print_path_min(int i){
while(i cout< i+=coin[path_min[i]];
}
cout<}


int main()
{
cout<<"**************************求最多最少硬币(递推法)**************************"< read();
cout< dp();
cout<<"最大硬币数及最小字典序DAG路径(面值):";
cout< print_path_max(0);
cout<<"最小硬币数及最小字典序DAG路径(面值):";
cout< print_path_min(0);
return 0;
}


热文推荐
猜你喜欢
友情链接: