C语言实例01背包与背包问题（贪心法）

很多朋友对于C语言实例01背包与背包问题（贪心法）和不太懂，今天就由小编来为大家分享，希望可以帮助到大家，下面一起来看看吧！

0-1背包问题：背包里要装的物品只有两种选择：全部装或者不装。

背包问题：对于要放入背包的物品，可以选择放入部分物品，不一定全部放入。

算法分析：

使用贪心策略解决此类问题时，首先必须选择最优的度量。

有三个指标可供选择：价值、容量、单位价值（v/w、价值/重量）。

显然，高价值的物品可能具有过多的容量，而大容量的物品可能具有较低的价值。最佳指标是单位值。

背包问题算法思路：

1、将每一项按照单位价值从高到低排序；

2、将价值最高的放入背包；

3.计算背包内剩余空间；

4、重复步骤2-3，直到背包剩余容量=0或者所有物品都装入背包（对于0-1背包，终止条件是背包剩余容量无法装下任何物品或所有物品）装入背包）。

以下是C语言实现（DEV c++4.9.9.2跑通）

#includestdio.h

void package(int n,float c,float v[],float w[],float x[]);

void package0_1(int n,float c,float v[],float w[],float x[]);

int 主函数（无效）

{

整数n=3;

浮动c=20;

浮动v[]={24,15,25};

float w[]={15,10,18};//已经按单位值降序排序

浮动*x；

x=(浮点*)malloc(sizeof(浮点)*n);

printf(‘*****背包*****\n’);

包（n，c，v，w，x）；

printf(‘********0-1背包******\n’);

package0_1(n,c,v,w,x);

系统（’暂停’）；

}

/*

* 背包问题

*n: 项目数量

* c: 背包容量

* v[]:每一项的值

* w[]:每件物品的重量（这里已经按单位值降序排列）

* 背包中是否放入x[]:个物品（0表示不放入，1表示全部放入，0-1表示部分放入）

*/

void package(int n,float c,float v[],float w[],float x[])

{

整数我；

for(i=0;in;i++)

{

x[i]=0;//初始状态，所有物品均未放入背包

}

for(i=0;in;i++)

{

如果(w[i]c)

{

休息；

}

x[i]=1；

c=c – w[i]；

printf(‘放入%d件物品，背包剩余容量为%f。\n’,(i+1),c);

}

if(i=n)//也可以放入item的一部分

{

x[i]=c/w[i];

printf(‘放入%d个物品的%f部分，背包剩余容量为0。\n’,(i+1),w[i]*x[i]);

}

}

/*

* 0-1背包问题

*n: 项目数量

* c: 背包容量

* v[]:每一项的值

* w[]:每件物品的重量（这里已经按单位值降序排列）

* x[]:件物品是否放入背包中（0表示不放入，1表示全部放入）

*/

void package0_1(int n,float c,float v[],float w[],float x[])

{

整数我；

for(i=0;in;i++)

{

x[i]=0;//初始状态，所有物品均未放入背包

}

for(i=0;in;i++)

{

如果(w[i]c)

{

休息；

}

x[i]=1；

c=c – w[i]；

printf(‘放入%d件物品，背包剩余容量为%f。\n’,(i+1),c);

}

}

虽然背包问题和0-1背包都具有最优子结构性质，但背包问题的最优解是利用贪心算法获得的。 0-1背包问题的最优解无法通过贪心算法得到，因为不能保证能够得到最终的解。装满背包并留下一些未使用的背包空间会降低整体价值。

————————–

用户评论

来自火星的我

这篇文章写的挺好的！把01背包问题的核心思想和贪婪法的思路解释得非常清晰，对于刚接触这种算法类型的同学来说很有帮助！ 代码也很简洁易懂

    有7位网友表示赞同！

厌归人

终于看到有人用简单直接的方式讲01背包 问题了！以前总是在各种复杂解法中迷茫，看来贪婪法真是一种高效的解决思路。

    有8位网友表示赞同！

醉枫染墨

c语言实现得不错，清晰易读，比我之前研究的那套代码简单多了 haha. 不知道有没有其他算法的实践例子?

    有20位网友表示赞同！

∞◆暯小萱◆

贪婪法虽然能找到比较好的结果，但是总感觉还差点儿意思，好像还能优化得更好！ 这里面涉及到的时间复杂度和空间复杂度分析也挺重要的。

    有19位网友表示赞同！

?娘子汉

背包问题真是有点深奥啊，看了这篇文章之后感觉终于开始明白它的本质了。 之前总是看着题目蒙在眼瞎…

    有17位网友表示赞同！

惯例

代码注释做得真不错，一下子就明白了算法逻辑是什么样子的，相比之前看那种乱七八糟的代码简直是天堂啊！

    有17位网友表示赞同！

微信名字

我一直在学习动态规划，之前看到01背包问题的时候还真的不知道该怎么下手，看了这篇文章后发现贪婪法也可以解决，感谢分享！

    有7位网友表示赞同！

从此我爱的人都像你

这个算法思路挺好的，但感觉实现起来还是有点复杂。 我想深入了解一下算法的时间复杂度，是否还有更优的解决方案？

    有15位网友表示赞同！

青瓷清茶倾城歌

c代码写得好啊，让我受益匪浅! 希望能看到其他问题的解题思路和示例, 例如组合问题等等

    有6位网友表示赞同！

放血

背包问题在实际应用中确实挺广泛的，理解它的原理对我来说很有意义。 这篇文章的例子非常清晰易懂，我记住了。

    有14位网友表示赞同！

_心抽搐到严重畸形っ°

虽然贪婪法能解决一部分01背包问题，但我想知道它在哪些场景下会失效？ 还有哪些其他有效的方法可以用来解决这个问题呢？

    有8位网友表示赞同！

君临臣

学习编程的第一步就是学好基础数据结构和算法，这篇文章很好的解释了背包问题的解题思路。 以后有机会要好好研究一下动态规划法。

    有20位网友表示赞同！

早不爱了

我比较疑惑贪婪法在一些特殊情况下会不会出现错误？ 我想看一个具体的实例来验证它的正确性

    有14位网友表示赞同！

歇火

写的太简单了吧！ 刚开始学习算法的时候，看了这么详细的例子就很容易理解了。 希望以后能看到更多这样的文章讲解其他算法吧!

    有10位网友表示赞同！

孤街浪途

我觉得这篇文章比较局限于01背包问题，能不能提供一些更广义的背包问题的解决方案？ 例如多重背包之类的问题

    有9位网友表示赞同！

猫腻

看了这篇文章后感觉贪婪法的思路还是很有用的，我想要应用到实际项目中，希望能找到更多它的应用场景:

    有16位网友表示赞同！

伤离别

虽然代码写的很简洁，但我对里面的参数设置和算法逻辑还是不太懂。 能提供更详细的解释吗？例如如何选择物品顺序?

    有5位网友表示赞同！