再见H胖胖

时间: 1ms        内存:128M

描述:

听H胖胖说H胖胖学长叨扰大家一年了,甚是内疚,于是H胖胖学长给大家买了一个礼物,给大家这两个学期的c语言程序设计画上圆满的句号。H胖胖学长看了看自己的口袋,有n个面值为a1,a2……an的金币各一枚,H胖胖学长想知道自己为了买这个礼物他的哪些硬币是必须被使用的,即H胖胖学长必须使用哪些金币。卖家不找零,只能恰好的金币总数。(本次为代码填空题,代码见提示,如果大家不用提示代码,欢迎大家自己尝试编写)提交全部代码,不是只有填空部分!

输入:

第一行是两个个整数n,x。(1 <= n <= 200,1<=x<=10000)。

第二行从小到大为n个整数a1,a2……an(1<=ai<=x)

输出:

第一行是一个整数,有多少个金币必须被使用的。

第二行是这些必须被使用的金币的面值(从小到大排列)。

注:输入数据将保证给定面值的硬币中至少有一种组合能恰好能够支付X元。
如果不存在必须被使用的硬币,则第一行输出0,第二行输出空行。

示例输入:

5 18
1 2 3 5 10

示例输出:

2
5 10

提示:

参考答案(内存最优[2024]):

#include<iostream>
#include<cstring>
using namespace std;
const int MAXPRICE = 10002; //最大物品价值
const int MAXN = 202;       //最大数量的金币个数
 
int main(){
    int dp[MAXPRICE];   //dp[j]表示价格为j的物品有几种面值的金币组成
    int coin[MAXN];     //coin[j]表示第j个金币的面值
    int unique[MAXN];   //unique[j]表示第j个必须使用金币的面值
    int ans[MAXPRICE];  //ans[j]表示dp[j]去掉某个金币的面值之后有几种面值的金币组成
    memset(dp,0,sizeof(dp));    //初始化dp数组所有值为0
    dp[0] = 1;
    int n,x;
    int cnt = 0;
    cin >> n >> x;
    for(int i = 1 ; i <= n ; i++)   //输入每个金币的面值,从1开始
        cin >> coin[i];
    for(int i = 1; i <= n ; i++)
        for(int j = x ; j >= coin[i] ; j--)  //组成价格为x的物品有几种面值的金币组成
            dp[j] += dp[j-coin[i]];
    for(int i = 1 ; i <= n ; i++){
        for(int j = 0 ; j <= x ; j++)
            if(j < coin[i])
                ans[j] = dp[j];
            else
                ans[j] = dp[j] - ans[j-coin[i]];
        if(ans[x] == 0)
            unique[cnt++] = coin[i];
    }
    cout << cnt << endl;
    if(cnt > 0){
        for(int i = 0 ; i < cnt ; i++)
            if(i < cnt - 1 )
                cout << unique[i] << " ";
            else
                cout << unique[i] << endl;
    }else{
        cout << endl;
    }
    return 0;
}

参考答案(时间最优[3]):

#include<iostream>
#include<cstring>
using namespace std;
const int MAXPRICE = 10002; //最大物品价值
const int MAXN = 202;       //最大数量的金币个数
 
int main(){
    int dp[MAXPRICE];   //dp[j]表示价格为j的物品有几种面值的金币组成
    int coin[MAXN];     //coin[j]表示第j个金币的面值
    int unique[MAXN];   //unique[j]表示第j个必须使用金币的面值
    int ans[MAXPRICE];  //ans[j]表示dp[j]去掉某个金币的面值之后有几种面值的金币组成
    memset(dp,0,sizeof(dp));    //初始化dp数组所有值为0
    dp[0] = 1;
    int n,x;
    int cnt = 0;
    cin >> n >> x;
    for(int i = 1 ; i <= n ; i++)   //输入每个金币的面值,从1开始
        cin >> coin[i];
    for(int i = 1; i <= n ; i++)
        for(int j = x ; j >= coin[i] ; j--)  //组成价格为x的物品有几种面值的金币组成
            dp[j] += dp[j-coin[i]];
    for(int i = 1 ; i <= n ; i++){
        for(int j = 0 ; j <= x ; j++)
            if(j < coin[i])
                ans[j] = dp[j];
            else
                ans[j] = dp[j] - ans[j-coin[i]];
        if(ans[x] == 0)
            unique[cnt++] = coin[i];
    }
    cout << cnt << endl;
    if(cnt > 0){
        for(int i = 0 ; i < cnt ; i++)
            if(i < cnt - 1 )
                cout << unique[i] << " ";
            else
                cout << unique[i] << endl;
    }else{
        cout << endl;
    }
    return 0;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。