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

Question

当货物总重量∑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 <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 k;
printf("输入物品种数:\n");
scanf("%d",&n);
printf("输入背包重量:\n");
scanf("%f",&M);
printf("输入%d个物品的重量:\n",n);
for(k=0;k <n;k++)
scanf("%f",&w[k]);
printf("输入%d个物品的价值:\n",n);
for(k=0;k <n;k++)
scanf("%f",&p[k]);

while (flag != 0) /* 冒泡法 对单位价值进行排列*/
{
flag = 0;
for (k = 0; k < n-1; k++)
{
if (p[k]/w[k] < p[k+1]/w[k+1])
{
temp = p[k];
p[k] = p[k+1];
p[k+1] = temp;
temp = w[k];
w[k] = w[k+1];
w[k+1] = temp;
flag = 1;
}
}
}

printf("总价值最大是：%f\n",find(p,w,x,M,n));
for(k= 0; k < n; k++)
{
if(x[k]!=0)
{
printf("X%d: %f\n",k+1,x[k]);

}
}
return 0;
}
应该不是排序问题，主要是因为重新排序后，后来打印出来的X1，X2,X3对应的不是原来的W1,W2,W3.

Answer 1

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

你吧 原来的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(

Answer 2

分数太少了，第一个是动态规划，第二个是贪心，都挺简单的
还是给你写吧
第一题：
#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教你。本回答被网友采纳

Answer 3

分数太少了，第一个是动态规划，第二个是贪心，都挺简单的
还是给你写吧
第一题：
#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;
}
希望对你有帮助

Answer 4

答案是正确的 程序没有出错 是因为你的控制语句写错了 背包问题讲的是不能超过背包的总重量 三种物品的单位价值分别为1.2、1.5、1.25 挑选时先选1.5、1.25、1.2 重量分别为 10 8 最后才是2
建议你最好用一个数组对货物进行编号 这样分析时容易点 并且输出时清晰一点

Answer 5

你的冒泡排序貌似不对，你自己看一下排序后价值数组的数据看看