| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 1724 人关注过本帖
标题:贪心算法
只看楼主 加入收藏
dfmlpx
Rank: 1
等 级:新手上路
帖 子:9
专家分:7
注 册:2016-5-30
结帖率:50%
收藏
已结贴  问题点数:20 回复次数:3 
贪心算法
用贪心法求解最优分解问题:设n是一个正整数,现在要求将n分解为若干个互不相同的自然数之和,且使这些自然数的乘积最大。
求大神指教 这道题咋做??
搜索更多相关主题的帖子: 自然数 自然数 正整数 正整数 
2016-11-08 16:48
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:6 
在3和2之间考虑:3*3=9;2*2*2=8,它们的和都是6。

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-11-08 17:36
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来 自:长长久久
等 级:贵宾
威 望:52
帖 子:5023
专家分:14003
注 册:2016-10-22
收藏
得分:9 
不知道你所说的贪心算法是什么,但你可以看看我这种做法~就差检验有没有错了~
具体程序代码如下:
程序代码:
#include<stdio.h>
#include<math.h>
int main()
{
    int a,b,i;
    int max;
    printf("请输入被分解的数:");
    while (scanf("%d",&a)&&a<0)
        printf("不能输入负数,请重新输入!\n");
    b=a;
    a/=3;
    max=pow(3,a);
    if (b%3==1)
        max=max*4/3;
    if (b%3==2)max=max*2;
    printf("分解结果为:\nmax=");
    for (i=0;i<a-1;i++)
        printf("3*");
    if (b%3==0&&b)
        printf("3");
    if (b%3==1&&b>1)
        printf("2*2");
    if (b%3==2&&b>2)
        printf("3*2");
    if (b==2)
        printf("2");
    if (b==1)
        printf("1");
    if (b)printf("=%d\n",max);
    else 
        printf("0\n");
    return 0;
}

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2016-11-09 15:42
小灬志
Rank: 2
来 自:湖南
等 级:论坛游民
帖 子:6
专家分:16
注 册:2016-11-11
收藏
得分:5 
#include <iostream>
using namespace std;
int sort(int s[],int f[],int n)//把各个活动的起始时间和结束时间按结束时间递增排序
{
    int a,b;
    int i,j;
    for(i=0;i<n;i++)
    {
        for(j=i+1;j<n;j++)
        {
            if(f[i]>f[j])
            {
            a=f[i];f[i]=f[j];f[j]=a;
            b=s[i];s[i]=s[j];s[j]=b;
            }
        }
    }
}


int activemanage(int s[],int f[],bool a[],int n)
{
    a[0]=1;
    int i;
    int j=1,count=1;
    for(i=1;i<n;i++)
    {
        if(s[i]>=f[j])
        {
            a[i]=1;
            j=i;
            count++;
        }
        else a[i]=0;
    }
    return count;
}

int main()
{
    int i,n;
    int p;
    int s[100],f[100];
    bool a[100];
    cout<<"输入节目数:"<<endl;
    cin>>n;
    cout<<"请输入节目的开始和结束时间"<<endl;
    for(i=0;i<n;i++)
    {
        cin>>s[i];
        cin>>f[i];
    }
    sort(s,f,n);
    p=activemanage(s,f,a,n);
    cout<<"安排的节目个数为:%d\n"<<p<<endl;
    cout<<"节目的选取情况为(0表示不选 1表示选取)"<<endl;
    for(i=0;i<n;i++)
        cout<<a[i]<<endl;
}

2016-11-11 11:52
快速回复:贪心算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.058817 second(s), 8 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved