C语⾔之贪⼼算法（背包问题）
贪⼼算法
所谓贪⼼算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪⼼算法不是对所有问题都能得到整体最优解，但对范围相当⼴泛的许多问题他能产⽣整体最优解或者是整体最优解的近似解。贪⼼算法的基本思路如下：
1.建⽴数学模型来描述问题。
2.把求解的问题分成若⼲个⼦问题。
3.对每⼀⼦问题求解，得到⼦问题的局部最优解。
4.把⼦问题的解局部最优解合成原来解问题的⼀个解。
例题：
描述现在有很多物品（它们是可以分割的），我们知道它们每个物品的单位重量的价值v和重量w（1<=v,
w<=10）；如果给你⼀个背包它能容纳的重量为m（10<=m<=20），你所要做的就是把物品装到背包⾥，使背包⾥的物品的价值总和最⼤。
输⼊
第⼀⾏输⼊⼀个正整数n（1<=n<=5），表⽰有n组测试数据；
随后有n测试数据，每组测试数据的第⼀⾏有两个正整数s，m（1<=s<=10）;s表⽰有s个物品。接下来的s⾏每⾏有两个正整数v，w。
输出
输出每组测试数据中背包内的物品的价值和，每次输出占⼀⾏。
样例
1
3 15
5 10
2 8
3 9
输出
65
来源：
NYOJ
代码实现：
#include<stdio.h>
/*定义结构体物品*/
struct a
{
int v,w;//v为价值w为物品重量
} a[11];
int main()
{
int i,j,sum,s,m,n;
struct a t;
scanf("%d",&n);
while(n--)
{
sum=0;
scanf("%d%d",&s,&m);//s为物品个数，m，为背包容量        for(i=0; i<s; i++)
scanf("%d%d",&a[i].v,&a[i].w);c语言的冒泡排序算法
/*特别注意冒泡排序输出从⼤到⼩*/
for(i=0; i<s; i++)
{
for(j=i+1; j<s; j++)
{

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。