如果是使用网格背包实现的的背包界面，类似于《暗黑》这种背包，我是这么来定义结构的。发现和原来做的一个开纸的算法很类似，但是恰好反过来。反正没事儿想起来实现一下也不错。
一个物品的占位，默认左上角为（0,0）点。策划在填表的时候，只需要根据对角线关系填写（1,1）这个点就可以了。
class Item{
public:
int uid; //唯一ID
int quality; //品质
int pos[2]; //位于背包位置（左上角）
int isRota; //是否旋转
};
这样可以很方便的存储到一个map里面或者vector里面。
那么唯一的问题就是自动整理背包了！我是这么来排布背包的
每次放入背包一个物品，会将背包切割成两个区域，横向一个，下方一个，如果另起一行则会切割出来三个区域。占用一个格子的道具和物品，无论背包怎么整理这些物品都是能够放的下的。因为总的格子数是固定的。所以这些可以最后再填入。暂时不做考虑。
假设：存在n个不同品质的物品，占用标准如下，不考虑旋转，且保证背包（MAX_WIDTH,MAX_HEIGHT）能够放下,放不下舍弃。那么背包应该如何整理（不考虑旋转）。
输入：n个物品，数据结构如上
输出：n个物品，在背包内的位置信息，放不下的默认位置为（0,0）
算法描述，先横向放置，直到放置不下再换行放置。由于高度一致，从宽度大的往小的放，为了保证每一行都放满
根据MAX_WIDTH的奇偶性，分奇数先放还是偶数先放。
补充：为了保证新获得物品可以快速的放入到背包当中，其实可以存储一下int rightPos[2]，int bottoPos[2]这两个的位置信息。由于实际情况存在占用一个格子物品的情况。为了防止对算法的影响。占用单个格子的物品，默认从背包底行进行放置如果底行占满则从右列开始进行放置。
1: #include "stdafx.h"
2: #include <map>
3: #include <vector>
4: #define MAX_WIDTH 100
5: #define MAX_HEIGHT 100
6: const int INITPOS_0[2] = { 0, 0 };
7: const int INITPOS_1[2] = { 2, 0 };
8: const int INITPOS_2[2] = { 2, 1 };
9: const int INITPOS_3[2] = { 2, 2 };
10:
11:
12: class Item;
13: typedef std::map<int, Item*> ITEM_MAP;
14: typedef std::map<int, Item*>::iterator ITEM_ITERTOR_MAP;
15:
16: class Item
17: {
18: public:
19: int uid;
20: int quality;
21: int pos[2];
22: int init[2]; //占用位置
23:
24: Item(int uid_val, int quality_val, const int pos_val[2], const int init_val[2])
25: {
26: uid = uid_val;
27: quality = quality_val;
28: memcpy(pos, pos_val, sizeof(pos));
29: memcpy(init, init_val, sizeof(init));
30: }
31: };
32:
33: void sort(ITEM_MAP itemMap)
34: {
35: int rightPos[2] = { 0 }; //记录右侧剩余位置的起始
36: int bottoPos[2] = { 0 }; //记录底部剩余位置的起始
37: std::vector<Item*> initPos1Vec;//INITPOS_1 一组
38: std::vector<Item*> initPos2Vec;//INITPOS_2 一组
39: std::vector<Item*> initPos3Vec;//INITPOS_3 一组
40: for (ITEM_ITERTOR_MAP itor = itemMap.begin(); itor != itemMap.end(); itor++)
41: {
42: Item* item = itor->second;
43: if (item->init[1] == 0)
44: {
45: initPos1Vec.push_back(item);
46: }
47: else if (item->init[1] == 1)
48: {
49: initPos2Vec.push_back(item);
50: }
51: else if (item->init[1] == 2)
52: {
53: initPos3Vec.push_back(item);
54: }
55: }
56: if (MAX_WIDTH % 2)
57: {//奇数先放
58: //自己实现咯，保密
59: }
60: else
61: {//偶数先放
62: //自己实现咯，保密
63: }
64: return;
65: }
66:
67: void output(ITEM_MAP itemMap)
68: {
69: for (ITEM_ITERTOR_MAP itor = itemMap.begin(); itor != itemMap.end(); itor++)
70: {
71: Item* item = itor->second;
72: if (item->uid < 10)
73: {
74: printf("uid:0%d,quality:%d,pos:[%d,%d],init:[%d,%d] \n", item->uid, item->quality, item->pos[0], item->pos[1], item->init[0], item->init[1]);
75: continue;
76: }
77: printf("uid:%d,quality:%d,pos:[%d,%d],init:[%d,%d] \n", item->uid, item->quality, item->pos[0], item->pos[1], item->init[0], item->init[1]);
78: }
79: }
80:
81: int _tmain(int argc, _TCHAR* argv[])
82: {
83: ITEM_MAP itemmap;
84: for (int i = 0; i < 15; i++)
85: {
86: if (i < 5)
87: {
88: itemmap.insert(ITEM_ITERTOR_MAP::value_type(i + 1, new Item(i + 1, rand() % 3 + 1, INITPOS_0, INITPOS_1)));
89: continue;
90: }
91: if (i < 10)
92: {
93: itemmap.insert(ITEM_ITERTOR_MAP::value_type(i + 1, new Item(i + 1, rand() % 3 + 1, INITPOS_0, INITPOS_2)));
94: continue;
95: }
96: if (i < 15)
97: {
98: itemmap.insert(ITEM_ITERTOR_MAP::value_type(i, new Item(i, rand() % 3 + 1, INITPOS_0, INITPOS_3)));
99: }
100: }
101: sort(itemmap);
102: output(itemmap);
103: getchar();
104: return 0;
105: }
106:
原文：http://www.cnblogs.com/flashbird/p/4449050.html