가변 크기의 진리 값 테이블 만들기 및 채우기

Question

무차별 대항으로 0/1 배낭 문제를 해결하려고합니다. 가장 간단한 방법은 1과 0이 각각 배낭에 존재하고 존재하지 않는 것을 나타내는 2 차원 행렬을 설정하는 것입니다. 매개 변수는 항목 수 (즉, 열)이므로 행은 2^numOfItems 여야합니다. 그러나 항목 수가 일정하지 않으므로 행렬을 채우는 방법을 생각할 수 없습니다. 나는 비트 - 시프 팅이 효과가있을 것이라고 말했지만 어떻게 작동하는지 이해하지 못한다. 누군가 올바른 방향으로 나를 가리킬 수 있습니까?

편집 : 진리표에 의해 나는 이들 중 하나의 'A'부분 의미 : 당신은 매트릭스의 모든 비트 시퀀스를 저장하지 않아도 http://www.johnloomis.org/ece314/notes/devices/binary_to_BCD/bcd03.png

Answer 1

를, 그것은 불필요하고 너무 많은 메모리를 낭비 . 정수를 사용하여 현재 세트를 나타낼 수 있습니다. 정수는 0에서 2^n-1로 이동합니다. 여기서 n은 선택할 수있는 요소의 수입니다. 여기에 기본적인 아이디어가 있습니다.

int max = (1 << n); 
for(int set = 0; set < max; set++) 
{ 
    for(int e = 0; e < n; e++) 
    { 
     if((set & (1 << e)) != 0) 
      //eth bit is 1 means that the eth item is in our set 
     else 
      // eth element will not be put in the knapsack 
    } 
} 

알고리즘은 논리적 왼쪽 비트 이동에 의존한다. (1 << n)은 번호의 오른쪽에 0을 패딩하여 1, n 위치를 왼쪽으로 이동한다는 것을 의미합니다. 예를 들어, 1을 8 비트 숫자 00000001 (1 < <) == 00000010, (1 < < 2) == 00000100 등으로 표현하면 비트와 앤드 연산자는 두 개의 인수를 취하는 연산자입니다 , "ands"같은 인덱스를 가진 두 비트마다. 따라서 길이가 각각 n 인 2 비트 열이있는 경우 비트 0은 비트 0, 비트 1은 비트 1 등입니다. &의 출력은 두 비트가 모두 1 인 경우에만 1이되고, 그렇지 않은 경우 0입니다. 왜 이것이 유용한가 ?? 우리는 비트 검사를해야합니다. 예를 들어 비트 열로 표현 된 집합이 있다고 가정하고 비트 집합의 i 번째 비트가 1인지 0인지 결정하려고합니다. shift left 연산과 bitwise-and 연산을 사용하면됩니다.

예

세트 = 00101000 우리가 (3) (가장 오른쪽 비트가 비트 0 기억) 설정을 테스트하려면 우리가 할 수있는 그 왼쪽으로 1 ~ 3 장소를 이동하여, 그것은 00001000가되도록. 당신이 볼 수 있듯이 내가 테스트 오전 비트, 1, 다음 &의 출력이 제로가 아닌 것입니다 경우는 true, 그렇지 않은 경우는 제로가 될 것입니다 그리고 우리는 "을"를 설정

00101000 
     & 
00001000 
--------- 
00001000 

1이 이동 .