[数据结构与算法]【记忆化搜索】01背包 分组背包

01背包

LuoguOJ P1048 [NOIP2005 普及组] 采药

//记忆化搜索
//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define abss(x) ((x)>(0)?(x):(-1)*(x))
#define maxs(a,b) ((a)>(b)?(a):(b))
#define mins(a,b) ((a)<(b)?(a):(b))
#define FOR(i,a,b) for(register int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(register int i=(a);i>=(b);i--)
#define mem(a) memset(a,0,sizeof(a))
const int INF (1<<30);
const int inf (-1<<30);
using namespace std;

int vol[1007],val[1007],save[1007][1007];
int V,N;//V 背包容积，N 物品数量

int dfs(int OBJ,int VOL){//第obj个物品，背包剩余vol，dfs本身表示背包当前价值val
	if(VOL<0) return 0;
	if(OBJ>N) return 0;
	if(save[OBJ][VOL]!=0) return save[OBJ][VOL];
	int psb1,psb2=0;
	psb1=dfs(OBJ+1,VOL);
	if(VOL-vol[OBJ]>=0) psb2=dfs(OBJ+1,VOL-vol[OBJ])+val[OBJ];
	return save[OBJ][VOL]=max(psb1,psb2);
}

int main(){
	cin>>V>>N;
	FOR(i,1,N){
		cin>>vol[i]>>val[i];
	}
	int ANS=dfs(1,V);
	cout<<ANS<<endl;
	return 0;
}

分组背包

LuoguOJ P1757 通天之分组背包

#include<bits/stdc++.h>
#define abss(x) ((x)>(0)?(x):(-1)*(x))
#define maxs(a,b) ((a)>(b)?(a):(b))
#define mins(a,b) ((a)<(b)?(a):(b))
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define mem(a) memset(a,0,sizeof(a))
const int INF (1<<30);
const int inf (-1<<30);
using namespace std;

struct node{
	int vol,val;//体积，价值
}e[1001][1001];//第GRP组的第i件物品

int save[1001][1001];//记忆数组
int len[1001];//存储每组物品的个数（实际上就是m）
int n,m;//物品数量，背包容积
const int maxGRP=100;

int dfs(int GRP,int VOL){//第GRP组物品，剩余空间VOL
	if(save[GRP][VOL]!=0) return save[GRP][VOL];
	if(GRP>maxGRP) return 0;
	int res=dfs(GRP+1,VOL);

	for(int i=1;i<=len[GRP];i++){
		if(VOL<e[GRP][i].vol) continue;
		res=max(res,dfs(GRP+1,VOL-e[GRP][i].vol)+e[GRP][i].val);
	}
	return save[GRP][VOL]=res;
}
int main(){
	cin>>m>>n;
	int vol,val,grp;
	FOR(i,1,n){
		cin>>vol>>val>>grp;
		e[grp][++len[grp]]={vol,val};
	}
	cout<<dfs(1,m);
	return 0;
}

GxustOJ #382. 程序猿的工资

//#pragma GCC optimize(2)
#include<bits/stdc++.h>
#define abss(x) ((x)>(0)?(x):(-1)*(x))
#define maxs(a,b) ((a)>(b)?(a):(b))
#define mins(a,b) ((a)<(b)?(a):(b))
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define mem(a) memset(a,0,sizeof(a))
const int INF (1<<30);
const int inf (-1<<30);
using namespace std;

struct node{
	int vol,val;//体积，价值
}e[101][101];//第GRP组的第i件物品

int save[101][101];//记忆数组
int len[101];//存储每组物品的个数（实际上就是m）
int n,m;//组数，每组的个数

int dfs(int GRP,int VOL){//第GRP组物品，剩余空间VOL
	if(save[GRP][VOL]!=0) return save[GRP][VOL];
	if(GRP>n) return 0;
	int res=dfs(GRP+1,VOL);

	for(int i=1;i<=len[GRP];i++){
		if(VOL<e[GRP][i].vol) continue;
		res=max(res,dfs(GRP+1,VOL-e[GRP][i].vol)+e[GRP][i].val);
	}
	return save[GRP][VOL]=res;
}
int main(){
	cin>>n>>m;
	int tmp;
	FOR(i,1,n){
		FOR(j,1,m){
			cin>>tmp;
			e[i][++len[i]]={j,tmp};
		}
	}
	cout<<dfs(1,m);
	return 0;
}