一开始直接用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;
}
