가방 문제 시리즈 상세 설명

가방 문 제 는 가장 잘 풀 리 는 전형 적 인 문제 이다.통상 가장 많이 논의 되 는 가장 대표 적 인 가방 문 제 는 0 - 1 가방 문제 (0 - 1 Knapsack Problem) 다.그것 은 모든 가방 문제 와 관련 된 가방 문제 의 기초 이다.이 박문 은 0 - 1 가방 문 제 를 상세 하 게 분석 하고 0 - 1 가방 문제 의 몇 가지 해법 을 제시 하 는 동시에 0 - 1 가방 문제 의 의 미 를 연장 시 켜 완전 가방 문제 와 다 중 가방 문 제 를 풍부하게 하고 가방 문제 의 알고리즘 실현 과정 을 제시 하여 큰 도움 이 되 기 를 바란다.
질문
      N 개의 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 아 이 템 (아 이 템 당 1 개) 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 가 치 를 총화 할 수 있 는 지 알 아 보 세 요.가방 에 넣 을 아 이 템 을 선택 할 때 각 아 이 템 i 는 가방 에 넣 거나 가방 에 넣 지 않 는 두 가지 선택 만 있 습 니 다.아 이 템 i 를 가방 에 여러 번 넣 을 수 없고 일부 아 이 템 만 넣 을 수 없습니다.따라서 이 문 제 를 0 - 1 가방 문제 라 고 한다.
(1) 귀속 구 해
알고리즘 은 다음 과 같 습 니 다.

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6
using namespace std;
int nVol[GOODSNUM];
int nValue[GOODSNUM];


int knapsack(int itemIndex,int vol);


void main()
{
 int i=0,j=0;
 while(i<GOODSNUM)
 {
  cout<<"input the "<<i+1<<"th item(volume and value):";
  cin>>nVol[i]>>nValue[i];
  i++;
 }
 cout<<"The max value is: "<<knapsack(GOODSNUM,CAPACITY)<<endl;
}


int knapsack(int itemIndex,int vol)
{
 if (itemIndex==0||vol==0)
 {
  return 0;
 }
 else if (vol>=nVol[itemIndex] && knapsack(itemIndex-1,vol)<knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex])
  {
   return knapsack(itemIndex-1,vol-nVol[itemIndex])+nValue[itemIndex];
  }
 else 
  return knapsack(itemIndex-1,vol);
}

     분석: 귀속 구 해, 구 해 과정 중의 대부분 변 수 는 중복 구 해 과정 이 존재 하고 알고리즘 의 효율 이 비교적 낮 으 며 개선 이 필요 하 다.그럼 어떻게 개선 할 까요?가장 효과 적 인 것 은 매번 계 산 된 결 과 를 배열 로 저장 하고 중복 계산 을 하지 않 아 도 되 기 때문에 2 차원 배열 의 풀이 가 있다.
(2) 2 차원 배열 의 풀이
알고리즘 은 다음 과 같 습 니 다.

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6


using namespace std;


void main()
{
 int i=1,j;
 int v[GOODSNUM] = {10,12,40,40,40,15};
 int c[GOODSNUM] = {1,2,3,5,2,1};
 int fun[GOODSNUM+1][CAPACITY+1];
 for (i=1;i<=GOODSNUM;i++)
 {
  fun[i][0] = 0;
 }
 for (i=1;i<=CAPACITY;i++)
 {
  fun[0][i] = 0;
 }
 for (i=1;i<=GOODSNUM;i++)
 {
  for (j=1;j<=CAPACITY;j++)
  {
   if (j<c[i-1])
   {
    fun[i][j] = fun[i-1][j];
   }
   else if (fun[i-1][j]<fun[i-1][j-c[i-1]] + v[i-1])
    {
     fun[i][j] = fun[i-1][j-c[i-1]] + v[i-1];
    }
   else
    fun[i][j] = fun[i-1][j];
  }
 }
 cout<<"The max value is: "<<fun[GOODSNUM][CAPACITY]<<endl;
}

     분석: 2 차원 배열 의 구 해 방법 은 재 귀적 인 구 해 보다 훨씬 좋 지만 그 공간 복잡 도 는 여전히 비교적 높 고 계속 개선 할 여지 가 있 습 니까?1 차원 배열 이 가능 합 니까?답 은 긍정 적 이다.
(3) 1 차원 배열 의 풀이
알고리즘 분석:

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6


using namespace std;


void main()
{
 int nVolume[GOODSNUM] = {1,2,3,5,2,1};
 int nValue[GOODSNUM] = {10,12,40,40,40,15};
 int selectTable[GOODSNUM][CAPACITY+1] = {0};
 int nKnapsack[CAPACITY+1] = {0};//most important for the first compution below
 int itemIndex,capIndex;
 for (itemIndex=0;itemIndex<GOODSNUM;itemIndex++)
 {
  for (capIndex=CAPACITY;capIndex>=nVolume[itemIndex];capIndex--)//notice that capIndex>=nVolume[itemIndex],not capIndex>=0                
  {
   if (nKnapsack[capIndex]<nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex])
   {
    nKnapsack[capIndex] = nKnapsack[capIndex-nVolume[itemIndex]]+nValue[itemIndex];
    selectTable[itemIndex][capIndex] = 1;
   }
   else
    nKnapsack[capIndex] = nKnapsack[capIndex];
  }
 }
 cout<<"The max value is: "<<nKnapsack[CAPACITY]<<endl;
 cout<<"The selected items are: ";
 for (itemIndex = GOODSNUM-1,capIndex = CAPACITY;itemIndex>=0;itemIndex--)
 {
  if (selectTable[itemIndex][capIndex])
  {
   cout<<itemIndex+1<<" ";
   capIndex = capIndex - nVolume[itemIndex];
  }
 }
 cout<<endl;
}

    분석: 1 차원 배열 에서 공간 복잡 도 를 O (GOODSNUM * CAPACITY) 에서 O (CAPACITY) 로 낮 추고 코드 최적화 와 함께 아 이 템 선택 번호 도 제시 했다.
2. 완전 가방 문제
      0 - 1 가방 문제 와 그 깊 은 의 미 를 깊이 이해 하고 1 차원 배열 이 가방 문 제 를 해결 하 는 것 을 진정 으로 이해 할 수 있다 면 다음 문 제 는 당신 에 게 상당히 쉬 울 것 입 니 다.
      완전 가방 문제: N 가지 아 이 템 과 V 용량 의 가방 이 있 으 며, 모든 아 이 템 은 무한 개 사용 가능 합 니 다.제 i 종 물품 의 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 비용 을 합 쳐 가방 용량 을 초과 하지 않 고 가치 가 가장 큰 지 알 아 보 세 요.
     분석: 목 표 는 0 - 1 가방 문제 로 전환 하 는 것 이다.만약 에 비용 / 용량 이 nVolume [itemIndex] 인 물품 을 CAPACITY / nVolume [itemIndex] 와 같은 비용 과 가치 의 물품 으로 전환 하면 앞의 세 가지 0 - 1 가방 문제 로 직접 해답 을 구한다.이외에 또 다른 실행 가능 한 해답 방법 이 있 습 니까?0 - 1 가방 문제 의 상태 방정식 f [i] [v] = max {f [i - 1] [v], f [i - 1] [v - c [i]] + w [i]} 에 대해 완전한 가방 문 제 를 얻 을 수 있 는 상태 방정식 f [i] [v] = max {f [i - 1] [v - k * c [i]] + k * w [i] | 0 < = k * c [i] < = v} 을 약간 분석 할 수 있 기 때문에 다음 알고리즘 실현 과정 이 있 고 최종 적 으로 선택 한 물품 과 이 아 이 템 을 선택 하 는 수량 을 제시 했다.
구현 알고리즘:

#include "iostream"
#define CAPACITY 10
#define GOODSNUM 6


using namespace std;


void main()
{
 int num,k,max;
 int nVolume[GOODSNUM] = {1,4,3,5,5,3};
 int nValue[GOODSNUM] = {2,8,40,60,10,3};
 int selectTable[GOODSNUM][CAPACITY+1] = {0};
 int nKnapsack[CAPACITY+1] = {0};//most important for the first compution below
 int itemIndex,capIndex;
 for (itemIndex=0;itemIndex<GOODSNUM;itemIndex++)
 {
  for (capIndex=CAPACITY;capIndex>=nVolume[itemIndex];capIndex--)//notice that capIndex>=nVolume[itemIndex],not capIndex>=0
  {
   num = 0;
   max = nKnapsack[capIndex];
   for (k=1;k<=CAPACITY/nVolume[itemIndex];k++)
   {
    if (capIndex>=k*nVolume[itemIndex] && max<nKnapsack[capIndex-k*nVolume[itemIndex]]+k*nValue[itemIndex])
    {
     max = nKnapsack[capIndex-k*nVolume[itemIndex]]+k*nValue[itemIndex];
     num = k;
    }
   }
   nKnapsack[capIndex] = max;
   selectTable[itemIndex][capIndex] = num;
  }
 }
 cout<<"The max value is: "<<nKnapsack[CAPACITY]<<endl;
 cout<<"The selected items are: "<<endl;
 for (itemIndex = GOODSNUM-1,capIndex = CAPACITY;itemIndex>=0;itemIndex--)
 {
  if (selectTable[itemIndex][capIndex])
  {
   cout<<itemIndex+1<<":"<<selectTable[itemIndex][capIndex]<<" ";
   capIndex = capIndex - selectTable[itemIndex][capIndex]*nVolume[itemIndex];
  }
 }
 cout<<endl;
}

3. 다 중 가방 문제
      다 중 가방 문제: N 가지 아 이 템 과 V 용량 의 가방 이 있 습 니 다.제 i 종 아 이 템 은 최대 n [i] 개 를 사용 할 수 있 습 니 다. 모든 비용 은 c [i] 이 고 가 치 는 w [i] 입 니 다.어떤 물건 을 가방 에 넣 으 면 이 물건 들 의 비용 을 합 쳐 가방 용량 을 초과 하지 않 고 가치 가 가장 큰 지 알 아 보 세 요.
다 중 가방 문제 의 기본 적 인 해결 방식 은 완전 가방 문제 와 같 고 유일한 것 은 제어 파라미터 k 의 제한 이 다르다 는 것 이다.완전 가방 문 제 를 실현 하 는 것 만 있 으 면 됩 니 다.
제한 조건
4. 567913. 그러면 됩 니 다.