标题:关于C语言贪心算法
只看楼主
fuq349996693
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2016-3-11
结帖率:0
 问题点数:0 回复次数:4 
关于C语言贪心算法
背包问题。
设背包容量为C,共有n个物品,物品重量存放在数组W[n]中,价值存放在数组V[n]中,问题的解存放在数组X[n]中,贪心法求解背包问题的算法如下:
算法:贪心法求解背包问题
输入:背包的容量C,物品重量W[n],物品价值V[n]
输出:数组X[n]
改变数组W和V的排列顺序,使其按单位重量价值V[i]/W[i]降序排列;
数组X[n]初始化为0;
 i=0; 循环直到(W[i]>C)
  将第i个物品放入背包:X[i]=1;   C=C-W[i];  i++;  X[i]C/W[i]。
搜索更多相关主题的帖子: C语言 背包 价值 
2016-05-12 17:14
fuq349996693
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2016-3-11
得分:0 
2016-05-12 18:31
fuq349996693
Rank: 1
等 级:新手上路
帖 子:15
专家分:0
注 册:2016-3-11
得分:0 
2016-05-12 22:10
Alar30
Rank: 10Rank: 10Rank: 10
等 级:贵宾
威 望:10
帖 子:988
专家分:1627
注 册:2009-9-8
得分:0 
不懂什么是贪心法。。
2016-05-13 08:58
will丶
Rank: 6Rank: 6
等 级:侠之大者
威 望:8
帖 子:117
专家分:443
注 册:2015-10-19
得分:0 
程序代码:
int KnapSack (int W[],int V[],int N,int C)
{
    double X[10]={0};//将数组X[n]初始化为0
    int maxValue=0;
    for(int i=0;W[i]<C;i++)   
    {
        X[i]=1;
        maxValue+=V[i];
        C=C-W[i];
        
    X[i]=(double)C/W[i];
    maxValue+=X[i]*V[i];
    return maxValue;
    }
}


腾空类星陨,遥望若花生。
2016-05-13 13:06



参与讨论请移步原网站贴子:https://bbs.bccn.net/thread-464720-1-1.html




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

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