当前位置：首页 > article >正文

找零钱问题（C++）

article 2025/2/8 18:55:14

代码：

#include <iostream>
#include <iomanip>
using namespace std;
//找零钱问题动态规划算法
class Change{
public:
    Change(int n,int *p,int M); //构造函数
    int lookChange(); //动态规划方法求解能否付款    
    void show();      //显示求解备忘录和标记备忘录
    void traceBack(); //构造最优解
private:
    int *p,n,M;    //货币种数n，币值数组p，找零钱M
    int **F,**I;   //F记录表，I备忘录
};
Change::Change(int n,int *p,int M){//构造函数
    this->n = n;     //货币个数mSize，币值数组q，找零钱m
    this->p = p;
    this->M = M;
    F = new int*[n+1];  //分配n+1个一维数组
    I = new int*[n+1];  //分配n+1个一维数组
    for(int i=0;i<=n;i++){
        F[i] = new int[M+1];  //分配二维数组F[n+1][y+1]
        I[i] = new int[M+1];  //分配二维数组I[n+1][y+1]
    }
}
int Change::lookChange(){ //返回值：0无解,1有解
    //初始化 
	for(int j=1;j<=M;j++){  //初始化币值种类为0，均无解
        F[0][j] = 0; I[0][j] = 0;
    }
    for(int j=0;j<=n;j++){  //初始化找零钱0，均有解
        F[j][0] = 1; I[j][0] = 0;
    }
    for(int j=1;j<=M;j++){  //初始化只有一种币值，找零钱为此币值才有解
        if(p[0]==j){
            F[1][j]=1;
            I[1][j]=1;
        }
        else {
            F[1][j]=0;
            I[1][j]=0;
        }
    }
    //动态规划求解过程
    for(int k=2;k<=n;k++){
        for(int j=1;j<=M;j++){
            if(F[k-1][j]==1){
                F[k][j] = F[k-1][j];
                I[k][j] = I[k-1][j];
            }
            else if(F[k-1][j-p[k-1]]==1){
                F[k][j] = F[k-1][j-p[k-1]];
                I[k][j] = k;
            }
            else {F[k][j]=0;I[k][j]=0;}
        }
    }
     return F[n][M];
}
void Change::show(){ //显示能否找零钱和标记函数备忘录
    if(!F[n][M])return;
    cout<<"能否找零钱求解过程备忘录Fk(y)：\n   ";
    for(int i=0;i<=M;i++)cout<<setw(3)<<i; cout<<endl;
    for(int k=0;k<=n;k++){   //输出能否找零钱备忘录
        cout <<setw(3)<< k;
        for(int j=0;j<=M;j++)cout<<setw(3)<<F[k][j];
        cout<<endl;
    }
	cout<<endl;
    
	cout<<"\n标记函数备忘录Ik(y)：\n   ";
    for(int i=0;i<=M;i++)cout<<setw(3)<<i; cout<<endl;
    for(int k=0;k<=n;k++){   //输出标记函数备忘录
        cout <<setw(3)<< k;
        for(int j=0;j<=M;j++)cout<<setw(3)<<I[k][j];
        cout<<endl;
    }
	cout<<endl;
}
void Change::traceBack(){ //追踪解，并显示答案
	if (F[n][M]==0){
		cout << "不能付款" << endl;
		return;
	}         
    else {
    	int k = n, v = M;
    	cout << "用币值\"" << p[0];
        for(int i = 1; i < n; ++i) {
            cout << "," << p[i];
        }
        cout << "\"找零钱" << M << "，能付款，付款方案如下：";
		while(v != 0){
			k = I[k][v];
			cout << p[k-1] << " ";
			v -= p[k-1];
			k--;
		} 
	}
	cout << endl;
}
//教材P84习题3.6
int main(){
    int p[]={1,2,5,7}, y=10; //测试用例1
    //int p[] = {1,2,3,4,6,8,10,15,17,19}, y=45; //测试用例2
    int n = sizeof(p) / sizeof(int);

    Change Z = Change(n,p,y); //创建找零钱问题对象
	Z.lookChange(); //动态规划方法求解 
	Z.show();  //显示求解备忘录和标记备忘录
	  
	Z.traceBack();  //回溯追踪解，请待补充此追踪算法

    return 0;
}

运行结果：