1068. Find More Coins (30)-PAT甲级真题 巧妙思路 总耗时不超过4ms

1068. Find More Coins (30)-PAT甲级真题 巧妙思路

Eva loves to collect coins from all over the universe, including some other planets like Mars. One day she visited a universal shopping mall which could accept all kinds of coins as payments. However, there was a special requirement of the payment: for each bill, she must pay the exact amount. Since she has as many as 104 coins with her, she definitely needs your help. You are supposed to tell her, for any given amount of money, whether or not she can find some coins to pay for it.

Input Specification:

Each input file contains one test case. For each case, the first line contains 2 positive numbers: N (<=104, the total number of coins) and M(<=102, the amount of money Eva has to pay). The second line contains N face values of the coins, which are all positive numbers. All the numbers in a line are separated by a space.

Output Specification:

For each test case, print in one line the face values V1 <= V2 <= … <= Vk such that V1 + V2 + … + Vk = M. All the numbers must be separated by a space, and there must be no extra space at the end of the line. If such a solution is not unique, output the smallest sequence. If there is no solution, output “No Solution” instead.

Note: sequence {A[1], A[2], …} is said to be “smaller” than sequence {B[1], B[2], …} if there exists k >= 1 such that A[i]=B[i] for all i < k, and A[k] < B[k].
【题目大意】
用n个硬币买价值为m的东西，输出使用方案，使得正好几个硬币加起来价值为m。从小到大排列，输出最小的那个排列方案
【巧妙思路】

1. 正常思路是01背包，学的不好所以一开始的想法是正向枚举，比如要获得9，首先是只有一个硬币的遍历：有没有9；然后需要两个硬币，从1开始 有没有numbers[9-1]这个数，numbers是记录硬币币值的一个存储空间，有该数值，则numbers[该数值]=1，然后三个硬币，四个硬币。这时候可以灵机一动想为什么不能从最大的硬币个数来判断
2. 因为你想啊，两个硬币的币值大小 一定比一个硬币的币值大小小，之后会丢弃，比如27 45 一定比135大，那么我们就直接找最多的和为付款大小的硬币个数不就行了吗？直接反向枚举，直接找到符合条件的最多的硬币,135找到就直接输出完事儿
3. 那么你问了，从最多的开始算也不是很耗时间吗？那么我们可以用累加，得到一个数组sumv，sum[9]是前九个数【当然硬币得从小到大排列】，然后判断累加的和是不是大于m，while循环，直到当前这个sumv[index]的值小于m，那么机会来了，比如四个硬币 1234，要求10，那就直接1234找到了，两个硬币一个硬币三个硬币的就不管了！
4. 以sample为例

8 9
5 9 8 7 2 3 4 1

排完序 1 2 3 4 5 7 8 9
sum完 0 1 3 6 10 15 22 30 39
从39开始往前判断 发现3个数的时候刚好，那就找三个数开始有没有可能 1 2 4/ 1 3 5/1 4 7…或者四个硬币值，具体看代码 search函数，1 2 3 4…这样判断，从小到大来模拟，那么第一个找到的就是符合条件的最小的

5. 有一个坑，测试点6，可能所有硬币加起来都买不了，这样可能要从最大硬币值开始遍历，直接超时，建议先判断 if (sumv[digit] < m) ，加起来都不够你买的，直接输出NO
   
   应该算取巧了，耗时都不超过4ms，正规要学的就是01背包，还得练！

【正在刷题，记录日常，代码未简化，keep learing】

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

vector<vector<int>>result;
vector<int> v;
vector<int>sumv;
int numbers[100000];
int n, m;
vector<int>temp;
bool match = false;
void search(int i, int num, int digit) {
	if (digit == 1) {
		if (numbers[m - num] == 1) {
			temp.push_back(m - num);
			result.push_back(temp);
			//temp.pop_back();
			match = true;
		}
		return;
	}
	bool flag = true;
	for (int j = i; j < n && flag && !match; j++) {
		int newN = num + v[j];
		if (m - newN > v[j]) {
			temp.push_back(v[j]);
			search(j + 1, num + v[j], digit - 1);
			temp.pop_back();
		}
		else {
			return;
		}

	}
}

int main() {
	scanf("%d%d", &n, &m);
	v.resize(n);
	sumv.resize(n + 1);
	for (int i = 0; i < n; i++) {
		scanf("%d", &v[i]);
		numbers[v[i]] = 1;
	}
	sort(v.begin(), v.end(), less<>());
	for (int i = 0; i < n; i++) {
		sumv[i + 1] = sumv[i] + v[i];
	}
	int digit = n;
	if (sumv[digit] < m) {
		printf("No Solution");
		return 0;
	}
	while (sumv[digit] > m && digit >= 1) {
		digit--;
	}
	while (sumv[digit] <= m && digit >= 1 && !match) {
		search(0, 0, digit);
		digit--;
	}
	if (result.size() == 0) {
		printf("No Solution");
	}
	else {
		printf("%d", result[0][0]);
		for (int i = 1; i < result[0].size(); i++) {
			printf(" %d", result[0][i]);
		}
	}

	return 0;
}