[数据结构与算法]PAT 1068 Find More Coins (30 分)

DFS+剪枝

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e4+10;
int coin[maxn];                   //存储金币价值的数组 
int n,m;
bool vis[maxn]={false};                  //深搜时标记数组 
bool flag = false;                   //递归边界标志 
vector<int> ansPath;                    //保存ans 
int k;                              //k用来存储能用到的最大的金币的价值 
void dfs(int cur, vector<int> path, int w){//参数1 表示 第i枚金币；参数2 表示 ans数组；参数3表示已经组合到的金币的价值 
	if(flag) return;                   //如果flag为 true，直接结束。 
	vis[cur] = true;                  //将当前金币标记 为已访问(上次递归前已经加入到path数组 25行)
	//初始时cur为0，这个0号金币没加入path数组(前面没递归调用)。 
	if(w > m) return;               //组合价值超过 要买的商品的价值m，直接结束 
	if(w == m){
		flag = true;                //此处为设置递归结束标志 
		ansPath = path;             //找到题解，将其复制到ansPath全局数组中 
		return;
	}
	for(int i = cur+1; i<=k; i++){       //从下一个硬币开始dfs，之前的要么已经加入过，要么加入后结果!=m递归返回
		if(!vis[i]){                     // 如果vis[i] 为 false 
			path.push_back(coin[i]);
			dfs(i, path, w+coin[i]);     //递归 
			vis[i] = false;
			path.pop_back();
		}
	}
}
int main(){
	scanf("%d%d", &n, &m);
	long sum = 0;
	for(int i = 1; i<=n; i++){
		scanf("%d", &coin[i]);
		sum += coin[i];
	}
	if(sum < m) printf("No Solution");
	else {
	    sort(coin+1, coin+n+1);
		k = n;
		for(int i = 1; i<=n; i++)
			if(coin[i]>=m){
				k = i;              //面额比 第k个金币 大的金币都用不到，即k后面的金币都用不到 
				break;
			}
		dfs(0, ansPath, 0);
		if(flag){                   //如果flag为 true，说明找到满足要求的序列了 
			printf("%d", ansPath[0]);
			for(int i = 1; i<ansPath.size(); i++)
				printf(" %d", ansPath[i]);
		}
		else printf("No Solution");
	}	
	return 0;
}

使用的硬币数量最少

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n,m;
    cin>>n>>m;
    vector<int>coin(n+1);
    for(int i=1;i<=n;++i)
        scanf("%d",&coin[i]);
    sort(coin.begin()+1,coin.end());
    vector<int>dp(m+1,0);
    dp[0]=1;
    vector<vector<int>>compose(m+1);
    for(int i=1;i<=n;++i){
        for(int j=m;j>=coin[i];--j){
            if(dp[j-coin[i]]==1&&(compose[j-coin[i]].size()+1<compose[j].size()||compose[j].size()==0)){
                compose[j]=compose[j-coin[i]];
                compose[j].push_back(coin[i]);
            }
            dp[j]=dp[j]||dp[j-coin[i]];    
        }
    }
    if(dp[m]==1){
        for(int i=0;i<compose[m].size();++i){
            if(i==0) printf("%d",compose[m][i]);
            else printf(" %d",compose[m][i]);
        }
    }else{
        printf("No Solution");
    }
    return 0;
}