C语言 贪心算法求背包问题当货物总重量∑Wi小于或等于M时,把所有货物装入,总价值就达到最大.因此,关键是解决当总重量大于M时装货的方法.我们先从一个具体例子入手来研究一下本题的特

C语言 贪心算法求背包问题当货物总重量∑Wi小于或等于M时,把所有货物装入,总价值就达到最大.因此,关键是解决当总重量大于M时装货的方法.我们先从一个具体例子入手来研究一下本题的特
C语言 贪心算法求背包问题
当货物总重量∑Wi小于或等于M时,把所有货物装入,总价值就达到最大.因此,关键是解决当总重量大于M时装货的方法.
我们先从一个具体例子入手来研究一下本题的特点.
设n=3；M=20.
W1=15 W2=10 W3=8
P1=18 P2=15 P3=10
下面是我写的一个程序,不过好像有点问题,正确的结果应该是输出X1=2,X2=10,X3=8
但是输出的是：X1=10,X2=8,X3=2.
#include
#include
#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 k;
printf("输入物品种数:\n");
scanf("%d",&n);
printf("输入背包重量:\n");
scanf("%f",&M);
printf("输入%d个物品的重量:\n",n);
for(k=0;k

C语言 贪心算法求背包问题当货物总重量∑Wi小于或等于M时,把所有货物装入,总价值就达到最大.因此,关键是解决当总重量大于M时装货的方法.我们先从一个具体例子入手来研究一下本题的特
分数太少了,第一个是动态规划,第二个是贪心,都挺简单的
还是给你写吧
第一题：
#include<stdio.h>
#include<memory.h>
int a[2000],b[200000],n,m,i,j;
int main()
{
scanf("%d",&n);//钱币种类
for (i=0;i<n;i++)
scanf("%d",&a[i]);//每个钱币的面值
scanf("%d",&m);//需要计算的钱币的面值
memset(b,0,sizeof(b));
for (i=0;i<n;i++)
b[a[i]]=1;
for (i=1;i<=m;i++)
for (j=0;j<n;j++)
if (i-a[j]>0)
if (b[i]==0)
{
if (b[i-a[j]]!=0)
b[i]=b[i-a[j]]+1;
}
else
{
if (b[i-a[j]]!=0&&b[i-a[j]]+1<b[i])
b[i]=b[i-a[j]]+1;
}
if (b[m]==0) printf("-1\n");//找不开输出-1
else printf("%d\n",b[m]);//可以找到交换策略,输出最小票数
return 0;
}
第二题：
#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;
}
我可以帮助你,你先设置我最佳答案后,我百度Hii教你.