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

分数太少了,第一个是动态规划,第二个是贪心,都挺简单的
还是给你写吧
第一题：
#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教你。