求一个算法(贪心算法)

首先,无所谓哪里密集哪里不密集的说法,这是人为的区分,需要首先遍历全部格子才能确定,是最慢的算法,全部遍历过了就可以得出最优的路线了

既然用贪心算法,为了思考方便,可以假设棋盘无穷大,算法的目的是判断下一步该往右走还是往下走，思想如下:

判断当前格子右、下两个相邻的格子是否有金块，情形如下：

1）如果一个有一个没有，则往有金块的格子走

2）如果都没有或都有，则需要判断往哪个方向走能更快的拾到下一个金块，方法如下：

让机器人假设地各往两个方向走一步，然后对当前格子作判断情形如下：

A)一个格子继续走能拾到金块，另一个不能，则上一步往该格子走

B)如果仍旧都有或都没有，重复2）直到找到符合A）的情形。

假设棋盘是NN个格子，则贪心算法最坏的情形是要遍历整个棋盘，比如只有第一个格子有金块时，就需要遍历整个棋盘才能确定走法。最好的情形也需要遍历4N个格子。

时间复杂度上来算的话，应该是O（nLogn）

void loading(W[],X[],c,n)

{

for(i=1,i<n,i++)

1void loading(int W[],int X[],int c,int n)

2没有定义i;

3for（;;）是冒号，非逗号

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=00,min=00;

for(i=1;i<=s;i++)result[i]=0};

for(i=1;i<=b;i++) {min+=buy[i]quantityprice[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]datacode)k++;

if(buy[k]code==offer[p][i]datacode) {

remain[k] =buy[k]quantity-offer[p][i]dataquantity;//保存剩余数量

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;

}

这可是咱老师的答案

import javautilArrays;

import javautilComparator;

//装箱问题，贪心算法

public class Enchase {

public void test1() {

Integer[] boxs={34,6,40,2,23,12,12};

以上就是关于求一个算法(贪心算法)全部的内容，包括:求一个算法(贪心算法)、贪心算法的最优装载问题、最少购物费用问题求解（贪心算法）等相关内容解答，如果想了解更多相关内容，可以关注我们，你们的支持是我们更新的动力！