再见H胖胖

再见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;
}

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