很多朋友对于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背包问题的最优解无法通过贪心算法得到，因为不能保证能够得到最终的解。装满背包并留下一些未使用的背包空间会降低整体价值。
————————–
原创文章，作者：小su，如若转载，请注明出处：https://www.sudun.com/ask/98477.html
用户评论
来自火星的我
这篇文章写的挺好的！把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位网友表示赞同！