‘壹’ 急，分全拿出来了，算法中的背包问题的贪心算法
#include <stdio.h>
#include <iostream.h>
#define MAXWEIGHT 20
#define n 3
float pw[n]={0},x[n]={0};
int w[n]={0},p[n]={0};
void sort(int p[],int w[])
{
int temp1,temp2;
float temp;
int i,j;
for(i=0;i<n;i++)
{
pw[i]=float(p[i])/w[i];
}
for(i=0;i<n-1;i++)
{
for(j=i+1;j<n;j++)
{
if(pw[i]<pw[j])
{
temp=pw[i],pw[i]=pw[j],pw[j]=temp;
temp1=p[i],temp2=w[i];
p[i]=p[j],w[i]=w[j];
p[j]=temp1,w[j]=temp2;
}
}
}
}
void GreedyKnapsack(int p[],int w[])
{
int m=MAXWEIGHT,i;
for(i=0;i<n;i++) x[i]=0.0;
for(i=0;i<n;i++)
{
if(w[i]>m) break;
x[i]=1.0;
m=m-w[i];
}
if(i<n) x[i]=float(m)/w[i];
}
void main()
{
int i;
printf("请输入每个物体的效益和重量:\n");
for(i=0;i<n;i++)
{
cin>>p[i]>>w[i];
}
for(i=0;i<n;i++)
{
printf("原物体%d的效益和重量分别为%d,%d:\n",i+1,p[i],w[i]);
}
sort(p,w);
printf("\n\n\n按效益值非递增顺序排列物体:\n");
for(i=0;i<n;i++)
{
printf("物体%d的效益和重量分别为%d,%d 效益值为:%f\n",(i+1),p[i],w[i],pw[i]);
}
GreedyKnapsack(p,w);
printf("\n\n\n最优解为:\n");
for(i=0;i<n;i++)
{
printf("第%d个物体要放%f:\n",i+1,x[i]);
}
}
这是正确的算法
‘贰’ 求背包问题贪心算法实例结果
找零钱问题：以人民币1元，2元，5元，10元，20元，50元，100元为例，要求所找的张数最少
背包问题：假设物体重量W1，W2．．．Wn其对应的价值为P1，P2．．．Pn，物体可分割，求装入重量限制为m的背包中的物体价值最大．可用P/W来解答．
#include<iostream>
#include<algorithm>
using namespace std;
struct good//表示物品的结构体
{
double p;//价值
double w;//重量
double r;//价值与重量的比
}a[2000];
double s,value,m;
int i,n;
bool bigger(good a,good b)
{
return a.r>b.r;
}
int main()
{
scanf("%d",&n);//物品个数
for (i=0;i<n;i++)
{
scanf("%lf%lf",&a[i].w,&a[i].p);
a[i].r=a[i].p/a[i].w;
}
sort(a,a+n,bigger);//调用sort排序函数，你大概不介意吧，按照价值与重量比排序贪心
scanf("%lf",&m);//读入包的容量m
s=0;//包内现存货品的重量
value=0;//包内现存货品总价值
for (i=0;i<n&&s+a[i].w<=m;i++)
{
value+=a[i].p;
s+=a[i].w;
}
printf("The total value in the bag is %.2lf.\n",value);//输出结果
return 0;
}
‘叁’ 贪心算法 部分背包问题
[背包问题]有一个背包，背包容量是M=150。有7个物品，物品可以分割成任意大小。
要求尽可能让装入背包中的物品总价值最大，但不能超过总容量。
物品 A B C D E F G
重量 35 30 60 50 40 10 25
价值 10 40 30 50 35 40 30
分析：
目标函数： ∑pi最大
约束条件是装入的物品总重量不超过背包容量：∑wi<=M( M=150)
（1）根据贪心的策略，每次挑选价值最大的物品装入背包，得到的结果是否最优？
（2）每次挑选所占重量最小的物品装入是否能得到最优解？
（3）每次选取单位重量价值最大的物品，成为解本题的策略。 ?
值得注意的是，贪心算法并不是完全不可以使用，贪心策略一旦经过证明成立后，它就是一种高效的算法。
贪心算法还是很常见的算法之一，这是由于它简单易行，构造贪心策略不是很困难。
可惜的是，它需要证明后才能真正运用到题目的算法中。
一般来说，贪心算法的证明围绕着：整个问题的最优解一定由在贪心策略中存在的子问题的最优解得来的。
对于例题中的3种贪心策略，都是无法成立（无法被证明）的，解释如下：
（1）贪心策略：选取价值最大者。反例：
W=30
物品：A B C
重量：28 12 12
价值：30 20 20
根据策略，首先选取物品A，接下来就无法再选取了，可是，选取B、C则更好。
（2）贪心策略：选取重量最小。它的反例与第一种策略的反例差不多。
（3）贪心策略：选取单位重量价值最大的物品。反例：
W=30
物品：A B C
重量：28 20 10
价值：28 20 10
根据策略，三种物品单位重量价值一样，程序无法依据现有策略作出判断，如果选择A，则答案错误。
‘肆’ 用贪心算法解决背包问题
用贪心算法解决背包问题，首先要明白，结果不一定是全局最优的。对于贪心法而言，首先步骤是找到最优度量标准，我这里的算法采用的最优度量标准是： 收益p/重量w 的值最大者优先放入背包中，所以有算法如下：void GreedyKnapsack(float * x){ //前置条件：w[i]已按p[i]/w[i]的非增次序排列 float u=m; //u为背包剩余载重量，初始时为m for(int i=0;i<n;i++) x[i]=0; //对解向量x初始化 for(i=0;i<n;i++){ //按最优度量标准选择的分量 if(w[i]>u) break; x[i]=1.0; u=u-w[i]; } if(i<n) x[i]=u/w[i];}
‘伍’ 关于一道C语言的背包问题，用的是贪心算法
#include "iostream.h"
#include "stdio.h"
#include <cstdlib>
struct stone
{
int name;
int weight;//物品的剩余重量
int weight_t;//物品的重量
float benefit;//物品的价值
//float b;
};
//按物品的效益排序
void sort(stone *data,int num)
{
//仅剩一个元素时排序完毕
if(num<1)
return;
int low=0,high=num;
stone key_s=data[low];//取数组的第一个作为关键字
float key=(float)key_s.benefit/key_s.weight;
int empty=low;//目标位置初始位置为low指向的位置
while(low<high)
{
if(low==empty)//后面的指针向前走
{
//找到比关键字小的元素把它移到low指向的位置
while((data[high].benefit/data[high].weight<key)&&(high>low))
{
high--;
}
if(data[high].benefit/data[high].weight>=key)
{
data[low]=data[high];
empty=high;
}
}
else if(high==empty)//前面的指针向后走
{
//找到比关键字大的元素把它移到high指向的位置
while((data[low].benefit/data[low].weight>=key)&&(low<high))
{
low++;
}
if(data[low].benefit/data[low].weight<key)
{
data[high]=data[low];
empty=low;
}
}
}
data[empty]=key_s;//把关键字放到划分完毕后两部分的中间位置
//关键字前面的数列继续递推
if(empty>1)
sort(data,empty-1);
//关键字后面的数列继续递推
if(num-empty-1>0)
sort(data+empty+1,num-empty-1);
}
//输入物品的信息
void inputstone(stone *bag,int num)
{
for(int i=0;i<num;i++)
{
bag[i].name=i+1;//物品的名字
printf("请输入第%d号物品的重量:",i+1);
scanf("%d",&bag[i].weight);
if (bag[i].weight<=0)
{printf("物品的重量必须大于0!\n");}
printf("请输入第%d号物品的价值:",i+1);
scanf("%f",bag[i].benefit);
if (bag[i].benefit<=0)
{printf("物品的价值必须大于0!\n");}
bag[i].weight_t=bag[i].weight;
}
}
//主函数
int main(int argc, char* argv[])
{ int i;
int num=0;//放入物品的数量
int weight=0;//背包可容纳的重量
float benefit=0;//总效益
stone *bag;//物品
/////输入背包可容纳的重量
do
{
printf("请输入背包可容纳的重量:");
scanf("%d",&weight);
if (weight<=0)
printf("背包可容纳的重量必须大于0!\n");
}while(weight<=0);
//输入物品种类
do
{
printf("请输入物品的数量:");
scanf("%d",&num);
if (num<=0)
printf("物品数量必须大于0!\n");
}while(num<=0);
bag=new stone[num];//物品数组
inputstone(bag,num);//输入物品的信息
sort(bag,num-1);//按单位效益排序
for(i=0;i<num&&weight>0;i++)
{
stone *temp=bag+i;
if(weight>=temp->weight)
{
weight-=temp->weight;
temp->weight=0;
benefit+=temp->benefit;
continue;
}
else
{
temp->weight-=weight;
weight=0;
benefit+=(temp->benefit*(1-(float)temp->weight/temp->weight_t));
break;
}
}
////////输出结果//////////
printf("物品种类 放入的比例 每单位效益 ");
for(i=0;i<num;i++)
{
stone *temp=bag+i;
printf("%d类物品",temp->name);
printf("\t\t%.2f\t\t",(temp->weight_t-temp->weight)/(float)temp->weight_t);
printf(" %.4f\n",temp->benefit/(float)temp->weight_t);
}
printf("总效益:%.2f",benefit);
delete bag;
getchar();
system("PAUSE");
return EXIT_SUCCESS;
return 0;
}
‘陆’ 动态规划背包问题与贪心算法哪个更优
首先这两个算法是用来分别解决不同类型的背包问题的，不存在哪个更优的问题。
当一件背包物品可以分割的时候，使用贪心算法，按物品的单位体积的价值排序，从大到小取即可。
当一件背包物品不可分割的时候，（因为不可分割，所以就算按物品的单位体积的价值大的先取也不一定是最优解）此时使用贪心是不对的，应使用动态规划。
‘柒’ 请问各位大虾:怎样用贪心算法解决背包问题
贪心只能解决物品可以分割的背包问题，01背包得用动态规划求解
‘捌’ 0-1背包问题具有贪心选择性质吗证明之
首先按物品的重量从小到大排序。贪心选择性质说的就是每次都是都是选取当前的最优值。假设背包问题每次都是从重量最小的物品开始选择的，那他一定满足贪心选择性质，假设背包问题不是从重量最小的物品开始选择的，那么说明重量最小的物品没有装入，现在我们用这个重量最小的物品代替当前选择装入的物品，依然可以得到一个最优解（装入的物品的个数相同）。所以背包问题具有贪心选择性质
‘玖’ 0/1背包问题能不能使用贪心法解决
贪心算法解决背包问题有几种策略：
(i)一种贪婪准则为：从剩余的物品中，选出可以装入背包的价值最大的物品，利用这种规则，价值最大的物品首先被装入（假设有足够容量），然后是下一个价值最大的物品，如此继续下去。这种策略不能保证得到最优解。例如，考虑n=2, w=[100,10,10], p =[20,15,15], c = 105。当利用价值贪婪准则时，获得的解为x= [ 1 , 0 , 0 ]，这种方案的总价值为2 0。而最优解为[ 0 , 1 , 1 ]，其总价值为3 0。
(ii)另一种方案是重量贪婪准则是：从剩下的物品中选择可装入背包的重量最小的物品。虽然这种规则对于前面的例子能产生最优解，但在一般情况下则不一定能得到最优解。考虑n= 2 ,w=[10,20], p=[5,100], c= 2 5。当利用重量贪婪策略时，获得的解为x =[1,0], 比最优解[ 0 , 1 ]要差。
(iii)还有一种贪婪准则，就是我们教材上提到的，认为，每一项计算yi=vi/si,即该项值和大小的比，再按比值的降序来排序，从第一项开始装背包，然后是第二项，依次类推，尽可能的多放，直到装满背包。
有的参考资料也称为价值密度pi/wi贪婪算法。这种策略也不能保证得到最优解。利用此策略试解n= 3 ,w=[20,15,15], p=[40,25,25], c=30 时的最优解。虽然按pi /wi 非递（增）减的次序装入物品不能保证得到最优解，但它是一个直觉上近似的解。
而且这是解决普通背包问题的最优解，因为在选择物品i装入背包时，可以选择物品i的一部分，而不一定要全部装入背包，1≤i≤n。
‘拾’ 用贪心算法求解背包问题的最优解。
你这个是部分背包么？也就是说物品可以随意分割？
那么可以先算出单位重量物品的价值，然后只要从高价值到低价值放入就行了，按p[i]/w[i]降序排序，然后一件一件加，加满为止！
贪心的思路是：加最少的重量得到更大的价值！
算出单位价值为{6,4,3,2,7,5,2}
加的顺序即为5,1,6,2,3,4/7
如果重量不超过就全部都加，超过就加满为止
不懂可问望采纳！
推荐看dd_engi的背包九讲，神级背包教程！在此膜拜dd_engi神牛~