貪心算法設計與分析

1、南京信息工程大學 算法設計與分析 實驗(實習)報告實驗(實習)名稱 實驗(實習)日期 得分 指導老師 系 專業(yè) 班級 姓名 學號 一、 實驗目的：能夠熟悉貪心算法和最優(yōu)裝載算法二、 實驗內(nèi)容 貪心算法，背包問題package xd;import java.util.Arrays;import java.util.Scanner;public class XD public static void main(String args)Scanner in = new Scanner(System.in);System.out.println("Please enter the numbe

2、r of objects(請輸入物品的數(shù)量：)");int n = in.nextInt(); int w = new intn; int v = new intn; System.out.println("Now please enter the weight of the objects(現(xiàn)在請輸入這些物品的重量：)");for(int i=0;i<n;i+)wi = in.nextInt();System.out.println("Now please enter the value of the ojects(現(xiàn)在請輸入這些物品的價值：)&

3、quot;);for(int j=0;j<n;j+)vj = in.nextInt();System.out.println("Now please enter the capacity of the pack(請輸入背包的容積：)");int c = in.nextInt();double startTime = System.currentTimeMillis();int index = new intn;double r = new doublen; for(int k=0;k<n;k+)rk = vk/wk; indexk = k;double temp

4、 = 0;int x = 0;for(int i=0;i<n-1;i+)for(int j=i+1;j<n;j+)if(ri<rj)temp = ri;ri = rj;rj = temp;x = indexi;indexi = indexj;indexj = x;int w1 = new intn;int v1 = new intn;for(int i=0;i<n;i+)v1i = vindexi;w1i = windexi;int x1 = new intn; for (int i = 0; i < n; i+) x1i = 0; for(int i=0;i&l

5、t;n;i+)if(w1i<c)x1i = 1;c = c-w1i;System.out.println("The solution vector is(解向量是：)"+Arrays.toString(x1);int maxValue=0;for(int i=0;i<n;i+)if(x1i=1)maxValue = maxValue+v1i;System.out.println("Now,the max value of object in the pack is(背包可以容納的最大價值是：)"+maxValue);double endTim

6、e = System.currentTimeMillis();System.out.println("The Statements takes the time is(算法執(zhí)行所花費的時間為：)"+(endTime-startTime)+ " milliseconds!");最優(yōu)裝載import javax.swing.*;import java.io.*;import java.util.*;public class MaxLoading public static void main(String args) String s1=JOptionPan

7、e.showInputDialog(null,"請輸入貨物數(shù)量：", "最優(yōu)裝載",JOptionPane.QUESTION_MESSAGE); n=Integer.parseInt(s1); w=new int n; System.out.println("請輸出貨物的重量數(shù)組："); for(int i=0;i<n;i+)wi=(int)(100*Math.random();System.out.println(wi); String s2=JOptionPane.showInputDialog(null,"請輸入

8、第一艘輪船的載重量：", "最優(yōu)裝載",JOptionPane.QUESTION_MESSAGE); c=Integer.parseInt(s2); maxLoading(w,c,x); System.out.print("輸出當前最優(yōu)解:"); for(int i=1;i<n+1;i+)System.out.print(xi+" "); System.out.println(); System.out.println("最優(yōu)解："+bestw); static int n; static int

9、w; static int c; static int cw; static int bestw; static int r; static int x; static int bestx; public static int maxLoading(intww,int cc,intxx) n=ww.length-1; w=ww; c=cc; bestw=0; x=new int n+1; bestx=xx; for(int i=1;i<=n;i+) r+=wi; backtrack(1); return bestw; public static void backtrack(int i) if(i>n) if(cw>bestw) for(int j=1;j<