貪心算法JAVA 實(shí)現(xiàn)代碼

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;private int capacity;/背包容量pr

2、ivate float value;/背包內(nèi)價(jià)值private Random rand;public Bag()/自動(dòng)生成背包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(背包容量: +capacity);public

3、 float getvalue()return value;/*abstract class ComputeItemspublic List list = new ArrayList();/public */class Itemsprivate String imageStr;/物品名稱private int capacity;/物品空間private int value;/物品價(jià)值private Random rand;public Items(String s)/自動(dòng)生成物品rand = new Random ();this.imageStr = s;this.value = rand.n

4、extInt(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 getValue()return this.valu

5、e;public String getimageStr()return this.imageStr;public String toString()return +imageStr+: 容量為： +capacity+價(jià)值為： +value;interface Computefloat Sort();Map getMap();/重量優(yōu)先計(jì)算class Capa implements Computeprivate List list;private float array;/排序物品權(quán)值private Map mapItems ;/哈希表，用來存放物品權(quán)值與物品public Capa(List l

6、ist)this.list = list;mapItems = new HashMap();array = new floatlist.size();public float Sort()int i = 0;for(Items items:list)arrayi+ = items.getCapacity();/將物品權(quán)重放入數(shù)組mapItems.put(items.getCapacity(), items);/將物品權(quán)重與物品對象放入map對象Arrays.sort(array);/物品排序 升序return array;Overridepublic Map getMap() / TODO A

7、uto-generated method stubreturn mapItems;public String toString()return 重量優(yōu)先;/價(jià)值優(yōu)先計(jì)算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 float Sort()int i = 0;for

8、(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 價(jià)值優(yōu)先;/單位價(jià)值優(yōu)先class PreValue implements Computeprivate List list;private float

9、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);return array;Overridepub

10、lic Map getMap() / TODO Auto-generated method stubreturn mapItems;public String toString()return 單位價(jià)值優(yōu)先;/自定義優(yōu)先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 = list;this.f1 = f1;this.f2

11、 = 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);return array;Overridepublic M

12、ap getMap() / TODO Auto-generated method stubreturn mapItems;public String toString()return 自定義優(yōu)先級;class Showprivate static float array;private static Map map;/權(quán)值與物品對應(yīng)哈希表private static Map mapcard;/物品與JPanel對象對應(yīng)哈希表private static Bag bag ;/背包對象private int capacity;private float value;public Show(floa

13、t 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(裝包結(jié)果為：);for(int j = array.length ;j 0;j -)Float fx = arrayj-1;Items items = (Items)map.get(fx );/取對應(yīng)物品

14、權(quán)重值對應(yīng)物品對象Card c = (Card)mapcard.get(items);/權(quán)重值對應(yīng)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);elsefloat f1 = capacity/i

15、tems.getCapacity() *items.getValue();value = value + f1;c.Box.setSelected(true);System.out.println(2+items);System.out.println(剩余空間：+capacity);break;System.out.println(剩余容量為：+capacity+當(dāng)前價(jià)值為：+value);System.out.println(剩余容量為：v+capacity+當(dāng)前價(jià)值為：+value);return value;package txsf;import javax.swing.*;publi

16、c 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), image, TitledBorder.L

17、EADING, 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 = new JTextField();Cata.setE

18、ditable(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);Box = new JCheckBox(u88

19、C5u5165);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 JTextField CumValText;private JBu

20、tton 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;/背包生成 自動(dòng) 非自動(dòng)判斷boolean Itemboolean

21、 = false;/物品自動(dòng)生成 判斷int compute;/計(jì)算使用何種方式排序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 KeyListenerOverridepublic void keyPressed(

22、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 = new JPanel();panel.setBoun

23、ds(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, 121, 23);panel_3.add(C

24、ustomBag);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);AutoBag.setBounds(0, 0, 121

25、, 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, u8BF7u8F93u5165u80CCu5305u5BB9u91CF, T

26、itledBorder.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.addKeyListener(new KeyText();

27、/背包按鈕事件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(number);System.out.print

28、ln(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 = new JRadioButton(u8D28u91

29、CFu4F18u5148);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 CustomForm = new JRadioButton(u

30、81EAu5B9Au4E49);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;);JRadioButton PreValue = new JRad

31、ioButton(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);compute = 3;);JRadioButton

32、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(false);compute = 2;);JPa

33、nel 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), u7269u54C1u5BB9u91CFu6743u91CD, TitledBorder.LEADING

34、, 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(new KeyText();JPanel pan

35、el_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, 147, 36);panel_8.add(Valu

36、eText);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 ActionListener() public voi

37、d 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.valueOf(ValueText.getText().i

38、ntValue();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)+價(jià)值的物品;new Exceptions(null,str).setVisible(true);/new Exceptions(null,數(shù)據(jù)過多).se

39、tVisible(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, 394, 89);panel_1.add(pa

40、nel_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(true);Num.setEnabled(tru

41、e);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, TitledBorder.TOP, null,

42、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);panel_11.setLayout(null);JRa

43、dioButton 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);CusCampText.setEditabl

44、e(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, null, null);panel_12.s

45、etBounds(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), u8BF7u8F93u5165u7269u54C1u5BB9u91

46、CF, 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);CusCampText.addKeyListen

47、er(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 = new JTextField();CumValText.setEditable(false);CumValText.setBounds(0, 18, 178, 31);panel