『壹』 求找零钱问题和背包贪心算法问题（背包里物体可分解）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;
}
『贰』 最少购物费用问题求解（贪心算法）
type struct
{ int code;
int quantity;
}elem
elem buy [b]//b所购商品的种类数
type struct
{elem data ;
float gprice;
}group;
group offer [m][s]//m表示优惠策略的组数，s表示每组中的商品数
float price[n] ;//n表示商品的种类数
Mincost(data buy [], group offer [m][],int s,int b int result[])
{ int p,i,j,k, remain[b],flag=1;float cost=0.0,min=0.0;
for(i=1;i<=s;i++)result[i]=0};
for(i=1;i<=b;i++) {min+=buy[i].quantity*price[buy[i].code]; //计算优惠前花费
remain[i]= buy[i].quantity;}
while(flag){
flag=0;
for(p=1;p<=m;p++)
{ if(Match(p)) {//判断本次购买与各个组合是否匹配
k=1;
for(i=1;i<=s;i++) {
while(buy[k].code<offer[p][i].data.code)k++;
if(buy[k].code==offer[p][i].data.code) {
remain[k] =buy[k].quantity-offer[p][i].data.quantity;//保存剩余数量
if(remain[k] >=2) flag=1;
k++; } }
cost=gprice[p];
for(i=1;i<=b;i++) cost+=remain[i] *price[buy[i].code];//优惠后花费
if(cost<min){cost=min; result[p]=1;}
}//endfor(p)
for(i=1;i<=b;i++)buy[i].quantity=remain[i];
}}
int Match(int k)
{
int i,j=1;
for(i=1;i<=s;i++) {
while(buy[j].code<offer[k][i].code&&j<=b)j++;
if(j>b)break;
if(buy[j].code==offer[k][i].code)
if( buy[j].quantity>=offer[k][i].quantity)
j++;
else break;
}
if(i>s)return 1;
else return 0;
}
这可是咱老师的答案
『叁』 用贪心法做解决TSP问题
你好。
很幸来运看到你源的问题。
但是又很遗憾到现在还没有人回答你的问题。也可能你现在已经在别的地方找到了答案，那就得恭喜你啦。
对于你的问题我爱莫能助！
可能是你问的问题有些专业了。或者别人没有遇到或者接触过你的问题，所以帮不了你。建议你去问题的相关论坛去求助，那里的人通常比较多，也比较热心，可能能快点帮你解决问题。
希望我的回答也能够帮到你！
快过年了，
最后祝您全家幸福健康快乐每一天！
『肆』 贪心法求解问题应考虑哪几个方面
1、在符合条件的情况下能拿到最优解
2、 判断结束条件
『伍』 贪心算法 活动安排问题
这道题的贪心算法比较容易理解，我就不多说明了，只是提到一下算法思路1、建立数学模型描述问题。我在这里将时间理解成一条直线，上面有若干个点，可能是某些活动的起始时间点，或终止时间点。在具体一下，如果编程来实现的话，将时间抽象成链表数组，数组下标代表其实时间，该下标对应的链表代表在这个时间起始的活动都有哪些，具体参照程序注释。2、问题分解。为了安排更多的活动，那么每次选取占用时间最少的活动就好。那么从一开始就选取结束时间最早的，然后寻找在这个时间点上起始的活动，以此类推就可以找出贪心解。程序代码：#include<stdio.h>
struct inode //自定义的结构体
{
int end; //表示结束时间
inode *next; //指向下一个节点的指针
};int main()
{
inode start[10001],*pt;
int a,b,i,num=0; //num负责计数，i控制循环，a，b输入时候使用
for(i=0;i<10001;i++) //初始化
{
start[i].next=NULL;
}
while(scanf("%d %d",&a,&b)) //输入并建立数据结构
{
if(a==0&&b==0) break;
pt=new inode; //创建新的节点，然后将该节点插入相应的位置
pt->end=b;
pt->next=start[a].next;
start[a].next=pt;
}
i=0;
while(i<10001) //进行贪心算法，i表示当前时间
{
if(start[i].next==NULL)
{
i++; //该时间无活动开始
}
else
{
int temp=10001; //临时变量，存储该链表中最早的终止时间
for(pt=start[i].next;pt!=NULL;pt=pt->next)
{
if(pt->end<temp)
{
temp=pt->end;
}
}
i=temp; //将当前时间设置成前一子问题的终止时间
num++;
}
}
printf("%d\n",num); //打印结果
return 0;
}代码并不一定是最快速的，但是可以求出贪心解，如果你做的是ACM编程题目，不保证能AC注释我尽力写了，希望对你有帮助。