c背包问题贪心算法

❶ 贪心算法解决特殊0-1背包问题

void 0_1_Knapsack(float w[], int n, float c,int x[]) //w[]为每个物品的重量，c为背包容量
{
int i;
for(i=1;i<=n;i++) x[i]=0;
for(i=1;i<=n;i++)
{
if(w[i]>c) break;
x[i]=1;
c-=w[i];
}
}

❷ C语言 贪心算法求背包问题

是你的冒泡排序出了问题~

你吧 原来的1-2-3号按照东西的价值重新排列现在的1-2-3对应原来的2-1-3了
所以 你输出的时候是按 1-2-3输出的话 就等于第一个是原来的X2 第二个是X1第三个是X3
而且你的冒泡排序用错了 只比较了 P[0]/K[0]和P[1]/K[1] P[1]/K[1]和P[2]/K[2]
周一我去学校帮你重新改改 我家的机器没有C++
周一晚上我会上传答案~我最近正好也要做算法的作业~
#include <stdio.h>
#include <math.h>
#define N 50

float find(float p[N],float w[N],float x[N] ,float M,int n) /*先放单位价值量大的物体，再考虑小的物体*/
{
int i;
float maxprice;
for (i = 0; i < n; i++)
x[i] = 0;
i = 0;
maxprice=0;
while (i < n && w[i] < M)
{
M=M-w[i];
x[i] =w[i]; /* 表示放入数量 */
maxprice=maxprice+p[i];
x[n-1]=M;
i++;
}
if (i < n &&M> 0)
{
maxprice=maxprice+p[i]*x[i]/w[i];
i++;
}
return maxprice;
}

int main()
{
int n,flag=1;
float temp,M,w[N],p[N],x[N];
int a[N],b[N];
int k,j,l=0;
printf(

❸ 背包问题的贪心算法C＋＋

为啥不用动态规划呢？
背包的贪心法是每次都选择收益最大，如果包还能容纳，就放入包里面，并把这个物品去掉。

❹ 贪心算法中的背包问题求解答。C++代码

排序应该下面这样写
for(i=0;i<n-1;i++)
{
for(j=0;j<n-1-i;j++)
{
if(a[j]<a[j+1]))
{
//互换
temp = w[j];
w[j]=w[j+1];
w[j+1]= temp;
}
}
}

❺ 关于一道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;
}

❻ 为什么贪心算法不能解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=

❼ 贪心算法 部分背包问题

[背包问题]有一个背包，背包容量是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，则答案错误。

❽ C语言贪心算法 背包问题

if(k!=i)
t=T[i];
T[i]=T[k];
T[k]=t;
交换操作的三步要用{}括起来,不然只有t=T[i];是if的执行语句