一开始直接用01背包

后来发现这个物品和位置有关。

也就是价值不是固定的

后来看了题解

看了卡片最多就4

所以这是一个四维费用的背包，

每一维是卡片的数量

价值就是当前的位置的价值。

但是与常规的背包还是有点不同

代码中没有枚举物品这一项

实际上循环里面的四个卡片的判断语句就是枚举四个物品

这里是先体积后物品，保证了这四个物品只选了一件

分组背包中同一组内物品的循环顺序也是先提及后物品

#include<cstdio>

#include<cstring>

#include<algorithm>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

#define _for(i, a, b) for(int i = (a); i <= (b); i++)

using namespace std;

const int MAXN = 45;

const int MAXM = 360;

int f[MAXN][MAXN][MAXN][MAXN];

int num[MAXM], g[10], n, m, x;

void up(int& x, int a) { x = max(x, a); }

int main()

{

	scanf("%d%d", &n, &m);

	_for(i, 1, n) scanf("%d", &num[i]);

	_for(i, 1, m)

	{

		scanf("%d", &x);

		g[x]++;

	}

	f[0][0][0][0] = num[1];

	_for(a, 0, g[1])

		_for(b, 0, g[2])

			_for(c, 0, g[3])

				_for(d, 0, g[4])

				{

					int &t = f[a][b][c][d];

					int r = 1 + a + b * 2 + c * 3 + d * 4;

					if(a) up(t, f[a-1][b][c][d] + num[r]);

					if(b) up(t, f[a][b-1][c][d] + num[r]);

					if(c) up(t, f[a][b][c-1][d] + num[r]);

					if(d) up(t, f[a][b][c][d-1] + num[r]);

				}

	printf("%d\n", f[g[1]][g[2]][g[3]][g[4]]);

	return 0;

}