# 1068. Find More Coins (30)

150 ms

65536 kB

16000 B

Standard

CHEN, Yue

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, A, ...} is said to be "smaller" than sequence {B, B, ...} 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`
`0，1背包`
`按照字典序最小的输出方案，先把物品从大到小排序，然后再背包，就可以保证选的是字典序最小的，记录路径用二维数组`
```#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>

using namespace std;
int n,m;
const int maxn=1e4;
int a[maxn+5];
int dp;
int s[maxn+5];
void fun(int x,int y)
{
if(x>n)
return;
if(s[x][y]==1)
{
if(y-a[x]==0)
printf("%d\n",a[x]);
else
printf("%d ",a[x]);
fun(x+1,y-a[x]);
}
else
fun(x+1,y);

}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
}
sort(a+1,a+n+1);
memset(dp,-1,sizeof(dp));
memset(s,0,sizeof(s));
dp=0;
s=-1;
for(int i=n;i>=1;i--)
{
for(int j=m;j>=a[i];j--)
{
if(dp[j-a[i]]!=-1)
{
dp[j]=dp[j-a[i]]+a[i];
s[i][j]=1;
}

}
}
if(dp[m]==-1)
printf("No Solution\n");
else
fun(1,m);
return 0;
}```

493 篇文章45 人订阅

0 条评论

## 相关文章

### 1339 / 1163: [Baltic2008]Mafia

1163: [Baltic2008]Mafia Time Limit: 10 Sec  Memory Limit: 162 MB Submit: 96  Sol...

27850

### HttpEntity的类型及其使用

代表底层流的基本实体。通常是在http报文中获取的实体。他只有一个空参的构造方法。刚创建时没有内容，长度为负值。需要通过两个方法，把值赋进去。

1.1K10

### HDUOJ---1862EXCEL排序

EXCEL排序 Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (...

28380

### HDUOJ----2489 Minimal Ratio Tree

Minimal Ratio Tree Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768...

31160

### HDU 3782 xxx定律

xxx定律 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Jav...

36390

### PAT 甲级 1024 Palindromic Number

1024. Palindromic Number (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 ...

41060

### PAT 1009 Product of Polynomials

1009. Product of Polynomials (25) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16...

403110

421110

### Leetcode 268. Missing Number

Given an array containing n distinct numbers taken from 0, 1, 2, ..., n, find ...

228100

### 2017 Multi-University Training Contest - Team 9 1001&&HDU 6161 Big binary tree【树形dp+hash】

Big binary tree Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/65...

28560 