2 qq 22584569 qq_22584569 于 2016.05.04 18:21 提问

求解贪心算法相关问题

题目1: 已知X1,X2,X3,…,Xn是直线上的点,现希望用固定长度固定数量的木条去覆盖这些点,请编写程序求最多能够覆盖多少点?

输入要求:输入的第1行为三个整数n,m,k,分别表示直线上点的个数,木条的长度以及数量。输入的第2行有n个整数,表示坐标上的点。

输出要求:输出1行,为最多能够覆盖的点的个数。

输入样例:

8 3 2

10 7 6 1 -5 4 18 20

输出样例:

5

题目2:设n为一自然数,n可以分解成若干个不同的自然数的和,这样的分法有很多种,比如n=10, 10可以分解为:10=5+4+1; 10=5+3+2; 10+9+1; 10=8+2; 10=7+3; 10=6+4; 10=7+2+1; 10=6+3+1;…。在所有这些分法中,各加数乘积最大的为30, (10=5+3+2中加数的乘积为5*3*2=30)。试编写程序,求各种分解方法中各加数乘积的最大值。

输入要求:输入只有1行,自然数n。

输出要求:输出也只有1行,所有分解方法中各加数乘积的最大值。

题目3:有n个人参加一个马拉松接力游戏,游戏规定每个人可以根据自己的情况随时终止游戏并由下一个人继续接力。由于每个人的情况不同,即使同一个人也不可能在整个游戏过程中永远保持很好的状态。因此要求他们在比赛前根据每个人的情况需要制定一个接力规则,使整个比赛的时间越少越好。请编写程序帮助他们制定这样的接力方案。
输入要求:输入的第1行有三个整数n,k和m,分别表示参加接力的人的个数,每个人最多可以跑的公里数以及接力赛的距离(以公里为单位)。其后的n行,每行有k个整数,分别表示每个人跑整数1公里,2公里,….,K公里所花费的时间(以秒为单位,整数)。游戏要求每个人都必须参加比赛,且每次只能跑到整数公里后才能换人。
输出要求:输出1个整数,表示这些人跑完整个接力赛最少要花多少时间。

5个回答

lbcab
lbcab   2016.05.05 13:53
已采纳

题目2, 仅供参考:

 #include<iostream>
#include<vector>
using namespace std;

class MaxProductNumber {
public:
    MaxProductNumber() :
            maxNum(0) {
    }
    ~MaxProductNumber() {
    }
    int getTmpMaxNum();
    int getMaxProductNumber() {
        return maxNum;
    }
    bool isExistAtVec(int val);
    void Solution(int n, int curValue, int num);

public:
    int maxNum;           //保存最大乘积
    vector<int> vec;     //保存每次获取的n的拆分数
};

bool MaxProductNumber::isExistAtVec(int val) {
    if (vec.size() <= 0) {
        return false;
    }

    for (int i = 0; i < vec.size(); ++i) {
        if (val == vec.at(i)) {
            return true;
        }
    }
    return false;
}

int MaxProductNumber::getTmpMaxNum() {
    int tmpMax = 1;
    for (int i = 0; i < vec.size(); i++) {
        tmpMax *= vec.at(i);
        cout << vec.at(i) << " ";
    }
    cout << endl;
    return tmpMax;
}

void MaxProductNumber::Solution(int n, int curValue, int num) {
    if (num == n) {
        int tmp = getTmpMaxNum();
        if (tmp > maxNum) {
            maxNum = tmp;
        }
        return;
    }
    for (int i = curValue; i < n; i++) {
        if (!isExistAtVec(i)) {
            num += i;
            vec.push_back(i);
            Solution(n, curValue + 1, num);
            vec.pop_back();
            num -= i;
        }
    }
}

int main() {
    int n = 0;
    cin >> n;
    MaxProductNumber maxProduct;
    maxProduct.Solution(n, 1, 0);
    cout << maxProduct.getMaxProductNumber() << endl;
    return 0;
}

题目3, 与题目2其实相同, 只不过是又加了一个限制条件, 题目3可以翻译为:
将m公里数分解: m = 1 + 2 + 3..., m=1 + 1 + 1 ..., m=1+1+2+2.., 从所有的分解结果中找出分解数q的个数满足条件: q <= n, 然后在看这组数是否都小于k,
符合所有条件, 最后就获取到了花费的时间, 然后从就可以找到最少的花费时间了.
举个例子:
n=3
k=3
m=4
1 3 4
2 3 5
1 2 3
那么m可以拆解为: 1 1 1 1, 2 2, 1 3, 符合条件q <= n的是 2, 2 和 1 3, 对于2, 2这种情况 派第3个人跑2公里, 派第1个或第2个跑两公里, 共花费5.
对于1, 3这种情况, 派第3个人跑3公里, 第一个人跑1公里, 共花费4
综合最少时间为4

lbcab
lbcab 回复qq_22584569: 我给你把参考代码贴出来,你看一下, 不一定是正确的
一年多之前 回复
qq_27279883
qq_27279883 这里每个人都必须跑,所以q==n
一年多之前 回复
qq_22584569
qq_22584569 回复lbcab: 刚开始学,对算法什么的不太清楚。大神见谅!今晚有时间么?看了代码还能问问相关问题
一年多之前 回复
lbcab
lbcab 思路我已经描述了, 难道我描述的不清楚?? 有时间我再写参考代码, 连同问题1的..
一年多之前 回复
qq_22584569
qq_22584569 这个问题已经解决了。题目三应该在题目二的源程序上做哪些改动呢?
一年多之前 回复
qq_22584569
qq_22584569 题目2怎样才能做到只输出乘积最大的那一组分解结果呢?
一年多之前 回复
CSDNXIAOD
CSDNXIAOD   2016.05.04 18:32

贪心算法相关问题
----------------------biu~biu~biu~~~在下问答机器人小D,这是我依靠自己的聪明才智给出的答案,如果不正确,你来咬我啊!

dajiaxuejavascript
dajiaxuejavascript   2016.05.05 09:58

况不同,即使同一个人也不可能在整个游戏过程中永远保持很好的状态。因此要求他们在比赛前根据每个人的情况需要制定一个接力规则,使整个比赛的时间越少越好。请编写程序帮助他们制定这样的接力方案。
输入要求:输入的第1行有三个整数n,k和m,分别表示参加接力的人的个数,每个人最多可以跑的公里数以及接力赛的距离(以公里为单位)。其后的n行,每行有k个整数,分别表示每个人跑整数1公里,2公里,….,K公里所花费的时间(以秒为单位,整数)。游戏要求每个人都必须参加比赛,且每次只能跑到整数公里后才能换人。
输出要求:输出1个整数,表示这些人跑完整个接力赛

ZGZ1002
ZGZ1002   2016.05.05 10:39
qq_22584569
qq_22584569 能给解释解释么
一年多之前 回复
lbcab
lbcab   2016.05.06 13:42

仅供参考, 没有去仔细测过...

 #include<iostream>
#include<vector>
using namespace std;

class Result {
public:
    Result() :
        minTime(-1) {
    }
    ~Result() {
    }
    void setMinTime(int n, int k);
    int getMinTime() {
        return minTime;
    }
    void Solution(int m, int n, int k, int num);
    void setVecTime(int n, int k);
    void showVecTime(int n, int k);
    int getAllVecValue();
public:
    long minTime;           //保存最少消耗时间
    vector<int> vec;     //保存符合条件的拆分数
    vector<vector<long> > vecTime;  //保存每个人k公里跑的时间
};

void Result::showVecTime(int n, int k) {
    for (int i = 0; i < n; i++) {
        vector<long> vv = vecTime.at(i);
        for (int j = 0; j < k; j++) {
            cout<<vv.at(j)<<" ";
        }
        cout<<endl;
    }
}
void Result::setVecTime(int n, int k) {
    for (int i = 0; i < n; i++) {
        vector<long> vecc;
        int val;
        for (int j = 0; j < k; j++) {
            cin >> val;
            vecc.push_back(val);
        }
        vecTime.push_back(vecc);
    }
}

void Result::setMinTime(int n, int k) {
    //先判断所有的拆分数都小于k
    for(int i = 0; i < vec.size(); i++) {
        if (vec.at(i) > k) {
            return;
        }
    }

    int tmpTime = 0;
    vector<int> indexVec(n);
    for (int i = 0; i < vec.size(); i++) {
        long tmp = 1000000;
        int index = 0;
        for (int j = 0; j < n; j++) {
            if (indexVec.at(j) <= 0 && vecTime[j].at(vec.at(i) - 1) < tmp) {
                tmp = vecTime[j].at(vec.at(i) - 1);
                index = j;
            }
        }
        indexVec.at(index) = 1;
        index = 0;
        tmpTime += tmp;
    }

    if (minTime == -1 || minTime > tmpTime) {
        minTime = tmpTime;
    }
}

int Result::getAllVecValue() {
    int tmp = 0;
    for (int i = 0; i < vec.size(); i++) {
        tmp += vec.at(i);
    }
    return tmp;
}

void Result::Solution(int m, int n, int k, int num) {
    if (num >= m) {
        if (vec.size() == n && getAllVecValue() == m) {
            setMinTime(n, k);
        }
        return;
    }
    for (int i = 1; i <= m; i++) {
            num += i;
            vec.push_back(i);
            Solution(m, n, k, num);
            vec.pop_back();
            num -= i;
    }
}

/**
 * 测试数据
 * m=5 n=2 k=3
 * 1 2 3
 * 2 2 2
 */
int main() {
    int m, n, k;
    vector<vector<long> > vecTime;
    Result result;
    cin>>m>>n>>k;

    result.setVecTime(n, k);
    result.Solution(m, n, k, 0);
    cout <<result.getMinTime()<< endl;
    return 0;
}
lbcab
lbcab 回复qq_22584569: http://blog.csdn.net/jimo_lonely/article/details/51325089你看这个,就是题目1
一年多之前 回复
qq_22584569
qq_22584569 题目一我这找不到一点思路= =也查不到类似的题目诶
一年多之前 回复
Csdn user default icon
上传中...
上传图片
插入图片
准确详细的回答,更有利于被提问者采纳,从而获得C币。复制、灌水、广告等回答会被删除,是时候展现真正的技术了!