贪心算法解决部分背包问题(C语言，ruby)-阿里云开发者社区

贪心算法解决部分背包问题(C语言，ruby)

2017-11-15 3777

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，所做出的仅是在某种意义上的局部最优解。
贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。
贪心算法的基本思路如下：
1.建立数学模型来描述问题。
2.把求解的问题分成若干个子问题。
3.对每一子问题求解，得到子问题的局部最优解。
4.把子问题的解局部最优解合成原来解问题的一个解。

部分背包问题：
给定一个最大载重量为M的卡车和N种食品，有食盐，白糖，大米等。已知第 i 种食品的最多拥有Wi 公斤，其商品价值为Vi元/公斤，编程确定一个装货方案，使得装入卡车中的所有物品总价值最大。

分析：因为每一个物品都可以分割成单位块，单位块的利益越大显然总收益越大，所以它局部最优满足全局最优，可以用贪心法解答。方法如下：
（1）先将单位块收益按从大到小进行排序；
（2）初始化背包的剩余体积和当前价值；
（3）从前到后考虑所有物品：a.如果可以完全放入，当前价值加上物品总价值，剩余体积减去物品总体积；b.如果可以部分放进，当前价值加上物品价值*剩余体积，使剩余体积为0.

利用贪心策略解题，需要解决两个问题：
一、确定问题是否能用贪心策略求解；一般来说，适用于贪心策略求解的问题具有以下特点：
① 可通过局部的贪心选择来达到问题的全局最优解。运用贪心策略解题，一般来说需要一步步的进行多次的贪心选择。在经过一次贪心选择之后，原问题将变成一个相似的，但规模更小的问题，而后的每一步都是当前看似最佳的选择，且每一个选择都仅做一次。
② 原问题的最优解包含子问题的最优解，即问题具有最优子结构的性质。在背包问题中，第一次选择单位质量最大的货物，它是第一个子问题的最优解，第二次选择剩下的货物中单位重量价值最大的货物，同样是第二个子问题的最优解，依次类推。
二、如何选择一个贪心标准？正确的贪心标准可以得到问题的最优解，在确定采用贪心策略解决问题时，不能随意的判断贪心标准是否正确，尤其不要被表面上看似正确的贪心标准所迷惑。在得出贪心标准之后应给予严格的数学证明。

贪心一般都伴随着使用排序

C语言算法：

#include <stdio.h>
#include<stdlib.h>
#define MAXSIZE 100 //假设物体总数
#define M 20 //背包的载荷能力

//算法核心，贪心算法
void GREEDY(float w[], float x[], int sortResult[], int n)
{
float cu = M;
int i = 0;
int temp = 0;

for (i = 0; i < n; i++)//准备输出结果
{
x[i] = 0;
}

for (i = 0; i < n; i++)
{
temp = sortResult[i];//得到取物体的顺序
if (w[temp] > cu)
{
break;
}

x[temp] = 1;//若合适则取出
cu -= w[temp];//将容量相应的改变
}

if (i <= n)//使背包充满
{
x[temp] = cu / w[temp];
}

return;
}

void sort(float tempArray[], int sortResult[], int n)
{
int i = 0, j = 0;
int index = 0, k = 0;

for (i = 0; i < n; i++)//对映射数组赋初值0
{
sortResult[i] = 0;
}

for (i = 0; i < n; i++)
{
float temp = tempArray[i];

index = i;

//找到最大的效益并保存此时的下标
for (j = 0; j < n; j++)
{
if ((temp < tempArray[j]) && (sortResult[j] == 0))
{
temp = tempArray[j];
index = j;
}
}

//对w[i]作标记排序
if (sortResult[index] == 0)
{
sortResult[index] = ++k;
}
}

//修改效益最低的sortResult[i]标记
for (i = 0; i < n; i++)
{
if (sortResult[i] == 0)
{
sortResult[i] = ++k;
}
}

return;
}

//得到本算法的所有输入信息
void getData(float p[], float w[], int *n)
{
int i = 0;

printf("please input the total count of object: ");
scanf("%d", n);

printf("Please input array of p :\n");
for (i = 0; i < (*n); i++)
{
scanf("%f", &p[i]);
}

printf("Now please input array of w :\n");
for (i = 0; i < (*n); i++)
{
scanf("%f", &w[i]);
}

return;
}

void output(float x[], int n)
{
int i;

printf("\n\nafter arithmetic data: advise method\n");
for (i = 0; i < n; i++)
{
printf("x[%d]\t", i);
}

printf("\n");
for (i = 0; i < n; i++)
{
printf("%2.3f\t", x[i]);
}

return;
}

int main()
{
float p[MAXSIZE], w[MAXSIZE], x[MAXSIZE];
int i = 0, n = 0;
int sortResult[MAXSIZE];

getData(p, w, &n);

for (i = 0; i < n; i++)
{
x[i] = p[i] / w[i];
}

sort(x, sortResult, n);

GREEDY(w, x, sortResult, n);

output(x, n);
system("pause");

}

======Ruby代码

def sort_pw(count, p, w)
s=Hash.new
count.times do |i|
    s.store(i,p[i]/w[i].to_f)
end
seq=s.keys
1.upto(seq.length-1) do |i|
    (seq.length-i).times do |j|
      if s[seq[j]]<s[seq[j+1]]
        seq[j],seq[j+1] = seq[j+1],seq[j]
      end
    end
end
seq
end

def greedy(max_weight, seq, w)
rest=max_weight
result=[]
0.upto(seq.length-1) do |i|
    if rest>w[seq[i]]
      result[seq[i]]=rest/w[seq[i]]
      rest=rest%w[seq[i]]
    elsif rest<w[seq[i]]
      result[seq[i]]=rest/w[seq[i]].to_f
      rest=0
      break
    end
end
      return result
end

def calculate_benifits(result,p)
total_benifits=0
0.upto(p.length-1) do |i|
    if result[i]==nil
      result[i]=0
    end
    total_benifits+=result[i]*p[i]
end
total_benifits
end

puts "please input the total count of object:"
count=gets.chomp.to_i
puts "#{count}"
p=Array.new
w=Array.new
puts "Please input array of p:"
count.times do |i|
p[i]=gets.chomp.to_i
end
puts "Now please input array of w :"
count.times do |i|
w[i]=gets.chomp.to_i
end
puts "Please input bearing capacity of the bag: "
max_weight=gets.chomp.to_i
seq=sort_pw(count, p, w)
result= greedy(max_weight,seq, w)

total_benefits=calculate_benifits(result,p)

puts "In the following, we have #{count} kinds of items, 1 through #{count}.
Each kind of item j has a value pj and a weight wj."
0.upto(p.length-1) { |i| puts "p#{i+1}=#{p[i]}" }
puts "-----------------------------------------"
0.upto(w.length-1) { |i| puts "w#{i+1}=#{w[i]}" }
puts "The maximum weight that we can carry in the bag is #{max_weight}. "

puts "optimal solution is:"

0.upto(result.length-1) { |i| puts "result#{i+1}=#{result[i]}" }
puts "Total benifits is #{total_benefits}"

本文转自 fsjoy1983 51CTO博客，原文链接：http://blog.51cto.com/fsjoy/169700，如需转载请自行联系原作者

贪心算法解决部分背包问题(C语言，ruby)

热门文章

最新文章

相关课程

相关电子书

相关实验场景