greedy_bagdlg.h

背包算法

// greedy_bagDlg.h : header file
//

#if !defined(AFX_GREEDY_BAGDLG_H__19226A53_15E6_407D_9441_B934E14AF018__INCLUDED_)
#define AFX_GREEDY_BAGDLG_H__19226A53_15E6_407D_9441_B934E14AF018__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

/////////////////////////////////////////////////////////////////////////////
// CGreedy_bagDlg dialog

struct GoodsInfo//物品信息结构体
{
	int p;//物品的价值重量比
	int w;//物品的重量
	int x;//物品该放的数量
	int index;//物品编号
};

class CGreedy_bagDlg : public CDialog
{
// Construction
public:
	CGreedy_bagDlg(CWnd* pParent = NULL);	// standard constructor

// Dialog Data
	//{{AFX_DATA(CGreedy_bagDlg)
	enum { IDD = IDD_GREEDY_BAG_DIALOG };
	CListBox	m_result;
	CListBox	m_goods;
	int		m_k;
	//}}AFX_DATA

	// ClassWizard generated virtual function overrides
	//{{AFX_VIRTUAL(CGreedy_bagDlg)
	protected:
	virtual void DoDataExchange(CDataExchange* pDX);	// DDX/DDV support
	//}}AFX_VIRTUAL

// Implementation
protected:
	HICON m_hIcon;

	// Generated message map functions
	//{{AFX_MSG(CGreedy_bagDlg)
	virtual BOOL OnInitDialog();
	afx_msg void OnSysCommand(UINT nID, LPARAM lParam);
	afx_msg void OnPaint();
	afx_msg HCURSOR OnQueryDragIcon();
	virtual void OnOK();
	//}}AFX_MSG
	DECLARE_MESSAGE_MAP()
public:
	GoodsInfo *MyBuilt();
	void MySort(GoodsInfo goods[],int n);//按物品价值重量比从大到小排序
	int A[140];
	void Combination(GoodsInfo goods[],int m,int k);//产生子集
	int AllValue;//总价值
	int AllWeight;//背包能容纳总重量
	int temp_value,temp_weight;//临时价值和重量变量
	int BB[100];//存放放入背包物品位置
	int Weight;//最后背包总重量
};

//{{AFX_INSERT_LOCATION}}
// Microsoft Visual C++ will insert additional declarations immediately before the previous line.

#endif // !defined(AFX_GREEDY_BAGDLG_H__19226A53_15E6_407D_9441_B934E14AF018__INCLUDED_)