PAT 甲级 1068 Find More Coins(0,1背包)

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[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
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[105];
int s[maxn+5][105];
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]=0;
    s[0][0]=-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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏HansBug's Lab

1339 / 1163: [Baltic2008]Mafia

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

27850
来自专栏用户2442861的专栏

HttpEntity的类型及其使用

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

1.1K10
来自专栏ml

HDUOJ---1862EXCEL排序

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

28380
来自专栏ml

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
来自专栏cloudskyme

jbpm5.1介绍(7)

Junit测试评估流程 评估流程的界面如下: ? 这个示例里边用到了Script Task,Service Task和User Task Log执行记录日志的...

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

扫码关注云+社区

领取腾讯云代金券