『壹』 求找零錢問題和背包貪心演算法問題（背包里物體可分解）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注釋我盡力寫了，希望對你有幫助。