【 C 언어 DP 동적 기획 】 가방 문제 (01 가방, 다 중 가방, 완전 가방)

1. 모든 아 이 템 은 하나 뿐 이 므 로 놓 거나 놓 지 않 는 것 을 선택 할 수 있 습 니 다.(01 가방)
N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 물품 의 비용 은 a [i]. w 이 고 가 치 는 a [i]. value 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.
동적 계획 우 리 는 2 차원 배열 을 정의 합 니 다. 그 중에서 모든 요 소 는 하나의 상 태 를 대표 합 니 다. 즉, 앞의 i 개 물체 에 부 피 를 넣 는 것 이 j 가방 에서 가장 큰 가치 입 니 다.그 중에서 dp [0] [j] = 0, dp [i] [0] = 0 (부피 가 0 이 든 물품 이 없 든 보관 할 수 없 기 때문에 최대 가 치 는 0);이동 방정식:

if (a[i].w

순서

#include
struct node {
       int w,value;
	   int flag;
}a[100];
int dp[100][100]={0};
int c[100]={0};
void dpdist(int p,int q)
{
	int i,j;
    for(i=1;i<=p;i++)
	{
		for(j=1;j<=q;j++)
		{
		if(a[i].w>j)
			dp[i][j]=dp[i-1][j];
		else if(dp[i-1][j]>dp[i-1][j-a[i].w])
			dp[i][j]=dp[i-1][j];
		else
			dp[i][j]=dp[i-1][j-a[i].w]+a[i].value;
		}
	}
	printf("     %d
",dp[p][q]);
}
void trans(int p,int q)
{
	int i=p;
   while(p!=0)
   {
	   if(dp[p][q]>dp[p-1][q])
       {
		   c[p]=1;
		   q-=a[p].w;
	   }       
       p=p-1;
   }
   for(i;i>=1;i--)
   {
	   printf(" %d        ？%d",i,c[i]);
	   printf("
");
   
   }

}
int main()
{
	int i,p,q;
	scanf("%d %d",&p,&q);
	for(i=1;i<=p;i++)
	{
	scanf("%d %d",&a[i].w,&a[i].value);
	a[i].flag=i;
	}
	dpdist(p,q);
	trans(p,q);
	return 0;
}

2. 모든 물품 은 개 수 를 고정 시 켜 최대 가치 에 도달 하도록 한다.(다 중 가방)
한 층 더 순환 하여 개 수 를 판단 하면 프로그램 이 된다.

#include
struct node {
       int w,value,x;
	   int flag;
}a[100];
int dp[100][100]={0};
int cp[100][100]={0};
int c[100]={0};
void dpdist(int p,int q)
{
	int i,j,k;
         for(i=1;i<=p;i++)
	{
		for(j=1;j<=q;j++)
		{	
			for(k=0;k*a[i].value<=j&&k<=a[i].x;k++)
			{
                          if(dp[i][j]dp[p-1][q])
       {
		   c[p]=cp[p][q];
		   q-=a[p].w;
	   }       
       p=p-1;
   }
   for(i;i>=1;i--)
   {
	   printf(" %d     %d ？%d",i,c[i]);
	   printf("
");
   
   }

}
int main()
{
	int i,p,q;
	scanf("%d %d",&p,&q);
	for(i=1;i<=p;i++)
	{
	scanf("%d %d %d",&a[i].w,&a[i].value,&a[i].x);
	a[i].flag=i;
	}
	dpdist(p,q);
	trans(p,q);
	return 0;
}

3. 각 물품 의 수량 을 제한 하지 않 고 최대 가치 에 도달 하도록 한다.(완전 가방)
순서

#include
struct node {
       int w,value;
	   int flag;
}a[100];
int dp[100][100]={0};
int cp[100][100]={0};
int c[100]={0};
void dpdist(int p,int q)
{
	int i,j,k;
         for(i=1;i<=p;i++)
	{
		for(j=1;j<=q;j++)
		{	
			for(k=0;k*a[i].value<=j;k++)
			{
                          if(dp[i][j]dp[p-1][q])
       {
		   c[p]=cp[p][q];
		   q-=a[p].w;
	   }       
       p=p-1;
   }
   for(i;i>=1;i--)
   {
	   printf(" %d     %d ？%d",i,c[i]);
	   printf("
");
   
   }

}
int main()
{
	int i,p,q;
	scanf("%d %d",&p,&q);
	for(i=1;i<=p;i++)
	{
	scanf("%d %d",&a[i].w,&a[i].value);
	a[i].flag=i;
	}
	dpdist(p,q);
	trans(p,q);
	return 0;
}

삼중 순환 시간 이 복잡 한 것 같 습 니 다. 해결 방법 을 생각해 보고 업데이트 하 겠 습 니 다.