贪心算法JAVA实现代码

《贪心算法JAVA实现代码》由会员分享，可在线阅读，更多相关《贪心算法JAVA实现代码（18页珍藏版）》请在装配图网上搜索。

1、文档供参考，可复制、编制，期待您的好评与关注！ 贪心算法背包问题 java 代码package txsf;import java.util.*;public class Bag public int getCapacity() return capacity;public void setCapacity(int capacity) this.capacity = capacity;public float getValue() return value;public void setValue(float value) this.value = value + this.value;priv

2、ate int capacity;/背包容量private float value;/背包内价值private Random rand;public Bag()/自动生成背包rand = new Random();capacity = rand.nextInt(150);if(capacity 50)capacity += rand.nextInt(70);System.out.println(背包容量: +capacity);value = 0;public Bag(int capacity)/手工生成背包this.capacity = capacity;System.out.println

3、(背包容量: +capacity);public float getvalue()return value;/*abstract class ComputeItemspublic List list = new ArrayList();/public */class Itemsprivate String imageStr;/物品名称private int capacity;/物品空间private int value;/物品价值private Random rand;public Items(String s)/自动生成物品rand = new Random ();this.imageStr

4、 = s;this.value = rand.nextInt(50)+1;this.capacity = rand.nextInt(50)+1;System.out.println(s+: +this.capacity+ +this.value);public Items(String s,int capacity,int value)/手工生成物品this.imageStr = s;this.capacity = capacity;this.value = value;public float getCapacity()return this.capacity;public float ge

5、tValue()return this.value;public String getimageStr()return this.imageStr;public String toString()return +imageStr+: 容量为： +capacity+价值为： +value;interface Computefloat Sort();Map getMap();/重量优先计算class Capa implements Computeprivate List list;private float array;/排序物品权值private Map mapItems ;/哈希表，用来存放物

6、品权值与物品public Capa(List list)this.list = list;mapItems = new HashMap();array = new floatlist.size();public float Sort()int i = 0;for(Items items:list)arrayi+ = items.getCapacity();/将物品权重放入数组mapItems.put(items.getCapacity(), items);/将物品权重与物品对象放入map对象Arrays.sort(array);/物品排序 升序return array;Overridepubl

7、ic Map getMap() / TODO Auto-generated method stubreturn mapItems;public String toString()return 重量优先;/价值优先计算class Value implements Computeprivate List list;private float array;private Map mapItems ;public Value(List list)this.list = list;mapItems = new HashMap();array = new floatlist.size();public f

8、loat Sort()int i = 0;for(Items items:list)arrayi+ = items.getValue();mapItems.put(items.getValue(), items);Arrays.sort(array);return array;Overridepublic Map getMap() / TODO Auto-generated method stubreturn mapItems;public String toString()return 价值优先;/单位价值优先class PreValue implements Computeprivate

9、List list;private float array;private Map mapItems ;public PreValue(List list)this.list = list;mapItems = new HashMap();array = new floatlist.size();public float Sort()int i = 0;for(Items items:list)float f = items.getValue()/items.getCapacity();arrayi+ = f;mapItems.put(f, items);Arrays.sort(array);

10、return array;Overridepublic Map getMap() / TODO Auto-generated method stubreturn mapItems;public String toString()return 单位价值优先;/自定义优先class CustomForm implements Computeprivate List list;private float array;private Map mapItems ;float f1,f2;public CustomForm(List list,float f1,float f2)this.list = l

11、ist;this.f1 = f1;this.f2 = f2;mapItems = new HashMap();array = new floatlist.size();System.out.println(+list.size();public float Sort()int i = 0;for(Items items:list)float f = f1*items.getCapacity()+f2*items.getValue();System.out.println(f);arrayi+ = f;mapItems.put(f, items);Arrays.sort(array);retur

12、n array;Overridepublic Map getMap() / TODO Auto-generated method stubreturn mapItems;public String toString()return 自定义优先级;class Showprivate static float array;private static Map map;/权值与物品对应哈希表private static Map mapcard;/物品与JPanel对象对应哈希表private static Bag bag ;/背包对象private int capacity;private floa

13、t value;public Show(float array,Map map,Bag bag,Map mapcard)this.array = array;this.map = map;this.bag = bag;this.mapcard = mapcard;capacity = bag.getCapacity();value = bag.getValue();public float pack()System.out.println(装包结果为：);for(int j = array.length ;j 0;j -)Float fx = arrayj-1;Items items = (I

14、tems)map.get(fx );/取对应物品权重值对应物品对象Card c = (Card)mapcard.get(items);/权重值对应JPanel对象int i = capacity - (int)items.getCapacity();if(i 0)System.out.println(1+items);c.Box.setSelected(true);capacity = (int) (capacity - items.getCapacity();value = items.getValue()+value;System.out.println(剩余空间：+capacity);e

15、lsefloat f1 = capacity/items.getCapacity() *items.getValue();value = value + f1;c.Box.setSelected(true);System.out.println(2+items);System.out.println(剩余空间：+capacity);break;System.out.println(剩余容量为：+capacity+当前价值为：+value);System.out.println(剩余容量为：v+capacity+当前价值为：+value);return value;package txsf;im

16、port javax.swing.*;public class Card extends JPanelprivate JTextField Cata;private JTextField Value;private JLabel Label;public JCheckBox Box;private String image;private float catacity,value;public Card(String image,float f,float g) setBorder(new TitledBorder(UIManager.getBorder(TitledBorder.border

17、), image, TitledBorder.LEADING, TitledBorder.TOP, null, null);setBounds(new Rectangle(100, 0, 100, 100);this.image = image;this.catacity = f;this.value = g;setLayout(null);Label = new JLabel(New label);Label.setIcon(new ImageIcon(./img/+image+.png);Label.setBounds(1, 28, 64, 64);add(Label);Cata = ne

18、w JTextField();Cata.setEditable(false);Cata.setText(u5BB9u91CF+f);Cata.setBounds(61, 0, 66, 21);add(Cata);Cata.setColumns(10);Value = new JTextField();Value.setEditable(false);Value.setForeground(Color.BLACK);Value.setText(u4EF7u503C+g);Value.setBounds(61, 22, 66, 21);add(Value);Value.setColumns(10)

19、;Box = new JCheckBox(u88C5u5165);Box.setEnabled(false);Box.setBounds(71, 49, 103, 23);add(Box);package txsf;import javax.swing.*;public class Greedy_next extends JFrameprivate JTextField BagText;private JTextField CampText;private JTextField ValueText;private JTextField CusCampText;private JTextFiel

20、d CumValText;private JButton BagButton;private JButton StartCom;private JButton AddItems;private JComboBox Num;private JComboBox Spe;private JPanel pane;private String items = bless bottle chicken cloak glove HPPotion MPPotion ring shield star stock tree.split( );boolean bagboolean = false;/背包生成 自动

21、非自动判断boolean Itemboolean = false;/物品自动生成 判断int compute;/计算使用何种方式排序private Bag bag;private List list;private Compute compSort = null;public Map line;Card card;int count = 0;public Greedy_next() line = new HashMap();list = new ArrayList();pane = new JPanel();class KeyText implements KeyListenerOverrid

22、epublic void keyPressed(KeyEvent e) Overridepublic void keyReleased(KeyEvent e) Overridepublic void keyTyped(KeyEvent e) int keyChar=e.getKeyChar();if (keyChar=KeyEvent.VK_0 & keyChar=KeyEvent.VK_9) else e.consume(); / TODO Auto-generated method stubgetContentPane().setLayout(null);JPanel panel = ne

23、w JPanel();panel.setBounds(0, 0, 324, 284);getContentPane().add(panel);panel.setLayout(null);JPanel panel_3 = new JPanel();panel_3.setBounds(10, 5, 304, 98);panel.add(panel_3);panel_3.setLayout(null);JRadioButton CustomBag = new JRadioButton(u624Bu5DE5u751Fu6210u80CCu5305);CustomBag.setBounds(139, 0

24、, 121, 23);panel_3.add(CustomBag);CustomBag.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)BagText.setEnabled(true);BagText.setEditable(true);BagButton.setEnabled(true);bagboolean = true;);JRadioButton AutoBag = new JRadioButton(u81EAu52A8u751Fu6210u80CCu5305);Aut

25、oBag.setBounds(0, 0, 121, 23);panel_3.add(AutoBag);AutoBag.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)BagText.setEnabled(true);BagButton.setEnabled(true);bagboolean = false;);JPanel panel_5 = new JPanel();panel_5.setBorder(new TitledBorder(null, u8BF7u8F93u516

26、5u80CCu5305u5BB9u91CF, TitledBorder.LEADING, TitledBorder.TOP, null, null);panel_5.setBounds(10, 35, 140, 53);panel_3.add(panel_5);panel_5.setLayout(null);BagText = new JTextField();BagText.setEditable(false);BagText.setBounds(0, 23, 140, 30);panel_5.add(BagText);BagText.setColumns(10);BagText.addKe

27、yListener(new KeyText();/背包按钮事件BagButton = new JButton(u751Fu6210u80CCu5305);BagButton.setEnabled(false);BagButton.addActionListener(new ActionListener() public void actionPerformed(ActionEvent arg0) if(bagboolean)String s = BagText.getText();int number = Integer.valueOf(s).intValue();bag = new Bag(

28、number);System.out.println(number);elsebag = new Bag();BagText.setText(String.valueOf(bag.getCapacity(););BagButton.setBounds(188, 65, 93, 23);panel_3.add(BagButton);JPanel panel_4 = new JPanel();panel_4.setBounds(10, 113, 304, 162);panel.add(panel_4);panel_4.setLayout(null);JRadioButton ProCamp = n

29、ew JRadioButton(u8D28u91CFu4F18u5148);ProCamp.setBounds(6, 6, 121, 23);panel_4.add(ProCamp);ProCamp.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)StartCom.setEnabled(true);CampText.setEditable(false);ValueText.setEditable(false);compute = 1;);JRadioButton CustomF

30、orm = new JRadioButton(u81EAu5B9Au4E49);CustomForm.setBounds(155, 34, 121, 23);panel_4.add(CustomForm);CustomForm.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)StartCom.setEnabled(true);CampText.setEditable(true);ValueText.setEditable(true);compute = 4;);JRadioBu

31、tton PreValue = new JRadioButton(u5355u4F4Du4EF7u503Cu4F18u5148);PreValue.setBounds(6, 34, 121, 23);panel_4.add(PreValue);PreValue.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)StartCom.setEnabled(true);CampText.setEditable(false);ValueText.setEditable(false);com

32、pute = 3;);JRadioButton ProValue = new JRadioButton(u4EF7u503Cu4F18u5148);ProValue.setBounds(155, 6, 121, 23);panel_4.add(ProValue);ProValue.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)StartCom.setEnabled(true);CampText.setEditable(false);ValueText.setEditable(

33、false);compute = 2;);JPanel panel_6 = new JPanel();panel_6.setBounds(0, 58, 294, 60);panel_4.add(panel_6);panel_6.setLayout(new BoxLayout(panel_6, BoxLayout.X_AXIS);JPanel panel_7 = new JPanel();panel_7.setBorder(new TitledBorder(UIManager.getBorder(TitledBorder.border), u7269u54C1u5BB9u91CFu6743u91

34、CD, TitledBorder.LEADING, TitledBorder.TOP, null, null);panel_6.add(panel_7);panel_7.setLayout(null);CampText = new JTextField();CampText.setEditable(false);CampText.setBounds(0, 24, 147, 36);panel_7.add(CampText);CampText.setColumns(10);CampText.addKeyListener(new KeyText();CampText.addKeyListener(

35、new KeyText();JPanel panel_8 = new JPanel();panel_8.setBorder(new TitledBorder(null, u7269u54C1u4EF7u503Cu6743u91CD, TitledBorder.LEADING, TitledBorder.TOP, null, null);panel_6.add(panel_8);panel_8.setLayout(null);ValueText = new JTextField();ValueText.setEditable(false);ValueText.setBounds(0, 24, 1

36、47, 36);panel_8.add(ValueText);ValueText.setColumns(10);class Exceptions extends JDialogpublic Exceptions(JFrame parent,String s)super(parent,My dialog,true);setLayout(new FlowLayout();add(new JLabel(+s);setSize(200,100);StartCom = new JButton(u5F00u59CBu8BA1u7B97);StartCom.addActionListener(new Act

37、ionListener() public void actionPerformed(ActionEvent arg0) switch (compute)case 1:compSort = new Capa(list);break;case 2:compSort = new Value(list);break;case 3:compSort = new PreValue(list);break;case 4:float f1 = (float)Integer.valueOf(CampText.getText().intValue();float f2 = (float)Integer.value

38、Of(ValueText.getText().intValue();System.out.println(f1+f2);compSort = new CustomForm(list,f1,f2);Show s = new Show(compSort.Sort(),compSort.getMap(),bag,line);System.out.println(+compSort);float f = s.pack();String str = 背包中共有：+String.valueOf(f)+价值的物品;new Exceptions(null,str).setVisible(true);/new

39、Exceptions(null,数据过多).setVisible(true););StartCom.setEnabled(false);StartCom.setBounds(79, 129, 93, 23);panel_4.add(StartCom);JPanel panel_1 = new JPanel();panel_1.setBounds(334, 0, 410, 284);getContentPane().add(panel_1);panel_1.setLayout(null);JPanel panel_9 = new JPanel();panel_9.setBounds(6, 10,

40、 394, 89);panel_1.add(panel_9);panel_9.setLayout(null);JRadioButton AutoItems = new JRadioButton(u81EAu52A8u751Fu6210u7269u54C1);AutoItems.setBounds(6, 0, 121, 23);panel_9.add(AutoItems);AutoItems.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)AddItems.setEnabled(

41、true);Num.setEnabled(true);Spe.setEnabled(false);CusCampText.setEditable(false);CumValText.setEditable(false);Itemboolean = false;);JPanel panel_10 = new JPanel();panel_10.setBorder(new TitledBorder(UIManager.getBorder(TitledBorder.border), u9009u62E9u7269u54C1u7684u6570u91CF, TitledBorder.LEADING,

42、TitledBorder.TOP, null, null);panel_10.setBounds(255, 10, 129, 69);panel_9.add(panel_10);panel_10.setLayout(null);Num = new JComboBox();Num.setEnabled(false);Num.setBounds(0, 32, 129, 27);panel_10.add(Num);JPanel panel_11 = new JPanel();panel_11.setBounds(6, 109, 394, 111);panel_1.add(panel_11);pane

43、l_11.setLayout(null);JRadioButton CustomItems = new JRadioButton(u624Bu5DE5u751Fu6210u7269u54C1);CustomItems.setBounds(6, 6, 121, 23);panel_11.add(CustomItems);CustomItems.addActionListener(new ActionListener()public void actionPerformed(ActionEvent arg0)AddItems.setEnabled(true);Spe.setEnabled(true

44、);CusCampText.setEditable(true);CumValText.setEditable(true);Num.setEnabled(false);Itemboolean = true;list.removeAll(list);pane.removeAll();pane.repaint(););JPanel panel_12 = new JPanel();panel_12.setBorder(new TitledBorder(null, u9009u62E9u7269u54C1u79CDu7C7B, TitledBorder.LEADING, TitledBorder.TOP

45、, null, null);panel_12.setBounds(257, 6, 127, 49);panel_11.add(panel_12);panel_12.setLayout(null);Spe = new JComboBox();Spe.setEnabled(false);Spe.setBounds(0, 21, 127, 28);panel_12.add(Spe);JPanel panl = new JPanel();panl.setBorder(new TitledBorder(UIManager.getBorder(TitledBorder.border), u8BF7u8F9

46、3u5165u7269u54C1u5BB9u91CF, TitledBorder.LEADING, TitledBorder.TOP, null, null);panl.setBounds(6, 52, 181, 49);panel_11.add(panl);panl.setLayout(null);CusCampText = new JTextField();CusCampText.setEditable(false);CusCampText.setBounds(0, 18, 181, 31);panl.add(CusCampText);CusCampText.setColumns(10);

47、CusCampText.addKeyListener(new KeyText();JPanel panel_13 = new JPanel();panel_13.setBorder(new TitledBorder(null, u8BF7u8F93u5165u7269u54C1u4EF7u503C, TitledBorder.LEADING, TitledBorder.TOP, null, null);panel_13.setBounds(206, 52, 178, 49);panel_11.add(panel_13);panel_13.setLayout(null);CumValText =

48、 new JTextField();CumValText.setEditable(false);CumValText.setBounds(0, 18, 178, 31);panel_13.add(CumValText);CumValText.setColumns(10);CumValText.addKeyListener(new KeyText();AddItems = new JButton(u751Fu6210u7269u54C1);AddItems.setBounds(293, 251, 93, 23);panel_1.add(AddItems);AddItems.addActionLi

49、stener(new ActionListener()public void actionPerformed(ActionEvent arg0) /如果自动生成if(!Itemboolean)int number = Num.getSelectedIndex()+1;System.out.println(number);list.removeAll(list);pane.removeAll();pane.repaint();for(int i = 0;i 10)new Exceptions(null,数据过多).setVisible(true);AddItems.setEnabled(fals

50、e);setSize(100,100);String image = (String)Spe.getSelectedItem();Items it = new Items(image,Integer.valueOf(CusCampText.getText().intValue(),Integer.valueOf(CumValText.getText().intValue();list.add(it);Card card = new Card(it.getimageStr(),it.getCapacity(),it.getValue();line.put(it, card);System.out

51、.println(+image+ +CusCampText.getText()+ +CumValText.getText();card.setSize(100, 100);pane.add(card);pane.add(card);pane.repaint();pane.validate(););pane.setBounds(0, 304, 747, 300);getContentPane().add(pane);pane.setLayout(new GridLayout(2, 7, 0, 0);ButtonGroup b1 = new ButtonGroup();b1.add(AutoBag

52、);b1.add(CustomBag);ButtonGroup b2 = new ButtonGroup();b2.add(AutoItems);b2.add(CustomItems);ButtonGroup b3 = new ButtonGroup();b3.add(ProCamp);b3.add(ProValue);b3.add(PreValue);b3.add(CustomForm);for(String s: items)Spe.addItem(s);for(int i = 0;i 10;i +)Num.addItem(i+1);public static void main(String args) / TODO Auto-generated method stubGreedy_next g = new Greedy_next();g.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);g.setSize(800,600);g.setVisible(true);18 / 18