가방 문제 의 01 가방

가방 문제: 한 조 의 아 이 템 을 정 하고 모든 아 이 템 의 비용 과 가 치 는 다 릅 니 다. 아 이 템 을 어떻게 선택 하여 총 비용 을 제한 하지 않 는 조건 에서 마지막 총 가치 가 가장 큽 니까?
01 가방 은 가방 시리즈 의 기초 로 문 제 를 해결 하 는 사상 이 중요 하 다.01 가방 문 제 는 각 아 이 템 의 개 수 를 1 로 제한 합 니 다. 아 이 템 의 총 수량 N 과 한정 비용 V 를 알 기 시 작 했 습 니 다. 이어서 우 리 는 아 이 템 의 가치 val [i] 와 비용 vei [i] 를 얻 을 수 있 습 니 다.처음에 01 가방 을 접 했 을 때 자신 은 항상 욕심 을 떠 올 렸 다. 성 가 에 따라 높 은 것 에서 낮은 것 으로 순 서 를 매 긴 다음 에 앞의 몇 가지 물건 의 가 치 를 더 하면 된다.(실제 아 이 템 의 일 부 를 넣 을 수 있 는 가방 문 제 는 욕심 전략 으로 만 들 수 있 지만 01 가방 은 넣 거나 놓 지 않 는 문제 에 속 하기 때문에 DP 로 만 들 기 에 적합 합 니 다. 더 자세 한 분석 을 참고 하 시기 바 랍 니 다.http://blog.csdn.net/hy6688_/article/details/15427943) 그러나 이런 사고방식 은 엄밀 하지 않다. 예 를 들 어:
N=5   V=18
     wei: 14 12   2   3    4
     val: 28 24   3   4    5
val/wei:  2  2  1.5 1.3 1.25
이렇게 얻 은 결 과 는 28 로 31 이 최대 치 였 다.
N=3 V=18
wei:16 15 3
val:32 29 5
결 과 는 32, 진실 치 는 34.
욕심 을 부 리 는 사고방식 으로 하면 반드시 각 단계 에서 비용 V 가 충분 한 지 판단 해 야 한다. 설령 어느 단계 에 현재 의 물품 을 '자루' 에 넣 을 수 있다 하 더 라 도그러면 뒤의 더 좋 은 해석 을 차단 할 수도 있 습 니 다. 01 가방 문 제 를 해결 하 는 데 이렇게 중요 한 중간 분석 과정 이 있 습 니 다. i 번 째 물건 을 넣 거나 넣 지 않 는 것 은 원래 의 값 보다 크 거나 작 거나 가상 가방 이 많 습 니 다. i 번 째 물건 을 넣 을 수 있 는 가방 의 용량 은 V - wei [i] 입 니 다.모든 가방 을 시험 적 으로 놓 고 모든 아 이 템 에 대해 이러한 조작 을 하면 결 과 를 얻 을 수 있 습 니 다 Val [V]. 상태 이동 방정식: f [i] [w] = max (f [i - 1] [w - wei] + val [i], f [i - 1] [w]) 를 1 차원 배열 형식 으로 최적화 합 니 다: for (i = 1 - > N)
   for(j=V-->wei[i])
       Val[j]=max(Val[j-wei[i]]+val[i],Val[j]);
가방 (공간 이 다 되 었 습 니 다) 을 채 우 는 최 적 화 를 요구 하면 val [0] = 0 을 초기 화 합 니 다. 다른 모든 Val 은 - 0x3f3f3f3f3f3f (마이너스 무한) 입 니 다.
만약 에 공간 이 충분 한 상황 에서 가장 좋 은 해 를 요구한다 면 모든 Val 을 0 으로 초기 화 합 니 다. [한 물건 도 놓 지 않 으 면 가 치 는 당연히 0 입 니 다].
예:
항 저 우의 간단 한 01 가방 문제:http://acm.hdu.edu.cn/showproblem.php?pid=2602

#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int wei[1005],val[1005],Val[1005];
int zerone(int val[],int wei[],int N,int V){
    int i,j;
    memset(Val,0,sizeof(Val));
    for(i=0;i<N;i++){
        for(j=V;j>=wei[i];j--){ //              
            int tmp=Val[j-wei[i]]+val[i]; 
            Val[j]=tmp>Val[j]?tmp:Val[j];
        }
        //for(j=1;j<=V;j++)cout<<Val[j]<<" ";  cout<<endl;
    }
    return Val[V];
}
int main(int argc, char *argv[]) {
	//freopen("cin.txt","r",stdin);
	int T;
	scanf("%d",&T);
	while(T--){
		int N,V,i;
		scanf("%d%d",&N,&V);
		for(i=0;i<N;i++)scanf("%d",&val[i]);
		for(i=0;i<N;i++)scanf("%d",&wei[i]);
		int ans=zerone(val,wei,N,V);
		printf("%d
",ans);
	}
	return 0;
}