기초 가방 문제 정리

16000 단어 알고리즘
N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 물품 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.초기 화: 1. 가방 이 꽉 차 면 f [0] = 0, f [1 ~ V] = - INF 를 초기 화 합 니 다.2. 필요 하지 않 으 면 f [0 ~ v] = 0 을 채 웁 니 다.3. 마지막 f [V] > 0 은 가득 채 울 수 있다 는 것 을 의미한다.
int N, V,  c[MAXN],  w[MAXN],  f[MAXN];  //f[i]    i        

목차
가방
조 가방
완전 가방
다 중 가방
2 차원 비용 가방
01 가방
각 아 이 템 은 하나 뿐 이 므 로 놓 거나 놓 지 않 는 것 을 선택 할 수 있다.
int F() {
	memset(f, 0, sizeof(f));  
	for(int i = 1; i <= N; i++)  
		for(int j = V; j >= c[i]; j--)  
			f[j] = max(f[j], f[j-c[i]] + w[i]);
	return f[V];
}

패 킷
각 조 는 최대 한 개 만 가 져 갈 수 있다.
int F() {//G     , g[i] i       
	memset(f, 0, sizeof(f));  
	for(int i = 1; i <= G; i++)  
		for(int j = V; j >= 1; j--) 
			for(int k = 1; k <= g[i]; k++)  
				if(j >= c[i][k]) f[j] = max(f[j-c[i][k]] + w[i][k], f[j]);
	return f[V];	
}

완전 가방
각 아 이 템 은 무한 여러 번 넣 을 수 있 습 니 다.
int F() {
	memset(f, 0, sizeof(f));
    for(int i =1 ; i <= N ; i++)  
    	for(int j = c[i]; j <= V; j++)  
    		f[j] = max(f[j], f[j-c[i]]+w[i]);
    return f[V];
}

멀 티 백 팩
각 아 이 템 마다 일정 횟수 상한 이 있 습 니 다 n [i]
Void F() {  
    memset(f, 0, sizeof(f));  
    for(int i = 1; i <= N ; i++) 
    	for(int k = 1; k <= n[i] ; k++)  
            for(int j = V ; j >= c[i]; j--)  
            	f[j] = max( f[j], f[j-c[i]]+w[i] );  
    return f[V];
} 

2 차원 비용 가방
각 물품 의 소 모 는 두 개의 c1 과 c2 이 며, 총 용량 도 두 개의 V1, V2 가 있다.
int F() {
	memset(f, 0, sizeof(f));
    for(int i =1 ; i <= N ; i++)  
    	for(int j = V1; j >= c1[i]; j--)
    		for(int k = V2; k >= c2[i]; k--)  
    			f[j][k] = max(f[j][k], f[j-c1[i]][k-c2[i]] + w[i]);
    return f[V1][V2];
}
/*           ,    
for(int i = 0; i <= V1; i++)
	for(int j = 0; j <= V2; j++) 
		f[i][j] = -INF;    
f[0][0] = 0;
*/

좋은 웹페이지 즐겨찾기