그룹 가방 테마

해석

제목 배경: 아이템은 여러 조로 나뉘어져 있으며, 각 조는 하나의 해결 방법만 선택할 수 있습니다. 아래 코드 참조

T1 HDU1712

문제풀이

조별 배낭판

코드

#include
#define M 109
using namespace std;
int read(){
	int f=1,re=0;
	char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-'){f=-1;ch=getchar();}
	for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';
	return re*f; 
}
int n,m,f[M],a[M][M];
int main(){
	while(scanf("%d%d",&n,&m)){
		if(!n&&!m) break;
		memset(f,0,sizeof(f));
		for(int i=1;i<=n;i++) 
			for(int j=1;j<=m;j++) a[i][j]=read();
		for(int i=1;i<=n;i++)
			for(int j=m;j>=0;j--)
				for(int k=1;k<=m;k++)//         ，             
					if(j>=k) f[j]=max(f[j],f[j-k]+a[i][k]);
		printf("%d
",f[m]);
	}return 0;
}

T2 HDU3033

문제풀이

엄밀히 말하면 본 문제는 조별 배낭에 속하지 않고 조당 하나만 선택할 수 있는 제한이 없다. 반대로 조당 최소한 하나를 선택하는 제한이 있다.그러면 바로'f[i] [j] [j] = m a x (f[i] [j], f [i] [i] [j] [j] [i] [k]] + a [i] [k] + a [i] [i] [f[i] [i] [j] [k] + [k] [k] max(f[i][j], f[i][j-w[i][k]]+a[i][k], f[i-4.1][j-w[i][k]]]+a[i][k]f[i][j]f[i][j][j]f[j]f[i][j][j]전 iii조 물품이 jjj 용량을 써서 얻은 최대 가치를 나타낸다. w[i][k]w[i][k]w[i][k]는 ii조에서 kk조 물품의 무게를 나타낸다. v[i][k]v[k]v[i][k]는 ii조에서 kk 물품의 가치를 나타내는 동시에 초기화에 주의해야 한다. 왜냐하면 시작 상태를 제외하고 나머지 상태는 모두 비합법적인 상태이기 때문이다.

코드

#include
#define M 100009
using namespace std;
int read(){
	int f=1,re=0;
	char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-'){f=-1,ch=getchar();}
	for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';
	return re*f;
}
int f[12][M],a[12][M],n,m,tot[12],k,b[12][M],w;
int main(){
	while(~scanf("%d%d%d",&n,&m,&w)){
		memset(tot,0,sizeof(tot));
		for(int i=1;i<=n;i++){
			int x=read(),y=read(),z=read();
			a[x][++tot[x]]=y,b[x][tot[x]]=z;
		}memset(f,-1,sizeof(f));
		for(int i=1;i<=m;i++) f[0][i]=0;
		for(int i=1;i<=w;i++)
			for(int k=1;k<=tot[i];k++)
				for(int j=m;j>=0;j--){
					if(a[i][k]<=j&&f[i][j-a[i][k]]!=-1)
						f[i][j]=max(f[i][j],f[i][j-a[i][k]]+b[i][k]);
					if(a[i][k]<=j&&f[i-1][j-a[i][k]]!=-1)
						f[i][j]=max(f[i][j],f[i-1][j-a[i][k]]+b[i][k]);
				}
		if(f[w][m]<0) printf("Impossible
");
		else printf("%d
",f[w][m]);
	}return 0;
}

T3 P1757

문제풀이

조별 배낭판

코드

#include
using namespace std;
int read(){
	int f=1,re=0;
	char ch;
	for(ch=getchar();!isdigit(ch)&&ch!='-';ch=getchar());
	if(ch=='-'){f=-1;ch=getchar();}
	for(;isdigit(ch);ch=getchar()) re=(re<<3)+(re<<1)+ch-'0';
	return re*f; 
}
int m,n,w[109][1009],f[50009],v[109][1009],tot[109],k;
int main(){
	m=read(),n=read();
	for(int i=1;i<=n;i++){
		int x=read(),y=read(),z=read();
		w[z][++tot[z]]=x,v[z][tot[z]]=y;
		k=max(k,z);
	}
	for(int i=1;i<=k;i++)
		for(int k=m;k>=0;k--)
			for(int j=1;j<=tot[i];j++)
				if(k>=w[i][j]) f[k]=max(f[k],f[k-w[i][j]]+v[i][j]);
	printf("%d
",f[m]);
	return 0;
}