github 地址：https://github.com/iofu728/PAT-A-by-iofu728 难度：★★★★ 关键词：01 背包，动态规划

# 题目

1068.Find More Coins (30) 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].

Sample Input 1: 8 9 5 9 8 7 2 3 4 1

Sample Output 1: 1 3 5

Sample Input 2: 4 8 7 2 4 3

Sample Output 2: No Solution

# 大意

给出 n 个硬币的价值，求使得总价值=m 的选择策略。

# 思路

1. 如果硬币数量限定为 2 枚及以下，就可以用二分查找进行处理。
2. 不限定硬币数量这就是一个标准的动态规划问题，每个硬币只能用一次则是 01 背包问题。
3. choice[i][j]表示当前总价值 i，选择 j 个硬币的情况，w[]表示硬币价值，dp表示 i 项前的总价值。
4. 若dp[j-w[i]]+w[i]>=dp[j]，dp[j]=dp[j-w[i]]+w[i]，choice[i][j]=1。
5. 遍历得到dp[],然后选择最佳方案.

# code

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
const int maxn = 10010;
const int maxs = 110;
bool cmp(int a, int b) { return a > b; }
int main() {
  int n, m, dp[maxs], w[maxn],
      choice
          [maxn]
          [maxs];  // dp表示，w表示物品重量，choice表示第i个coin选择后总价值为j，存放的值为是否选择。
  fill(choice[0], choice[0] + maxs * maxn, 0);
  fill(dp, dp + maxs, 0);
  scanf("%d%d", &n, &m);
  for (int i = 0; i < n; ++i) {
    scanf("%d", &w[i]);
  }
  sort(w, w + n, cmp);
  for (int i = 0; i < n; ++i) {
    for (int j = m; j >= w[i]; --j) {
      if (dp[j - w[i]] + w[i] >= dp[j]) {
        dp[j] = dp[j - w[i]] + w[i];
        choice[i][j] = 1;
      }
    }
  }
  int MAX = -1, ans = -1;
  for (int v = 0; v <= m; v++) {
    if (dp[v] > MAX) {
      MAX = dp[v];
      ans = v;
    }
  }
  if (ans != m) {
    printf("No Solution\n");
    return 0;
  }
  bool flag[maxn] = {0};
  for (int i = n - 1; i >= 0; i--) {
    if (choice[i][ans] == 1) {
      flag[i] = true;
      ans -= w[i];
    }
  }
  int tag = 1;
  for (int i = n - 1; i >= 0; i--) {
    if (flag[i] == true) {
      if (tag)
        tag = 0;
      else
        printf(" ");
      printf("%d", w[i]);
    }
  }

  return 0;
}