0 - 1 가방 문제
― 가방 에 들 어 가 는 아 이 템 을 어떻게 선택해 야 가방 에 들 어 가 는 아 이 템 의 총 가치 가 가장 큽 니까?
한 파 를 분석 하면 모든 물품 에 대해 우 리 는 두 가지 선택 을 선택 하거나 가 져 오지 않 을 뿐 특정한 물품 의 일부분 을 선택 할 수 없고 같은 물품 을 여러 번 불 러 올 수 없다.
해결 방법: 크기 를 설명 합 니 다. m [n] [c] 의 2 차원 배열, m [i] [j] 는 제 i 물품 을 직면 하고 있 으 며 가방 용량 은? j 시 얻 을 수 있 는 최대 가치 ，그러면 우 리 는 m [i] [j] 의 계산 방법 을 쉽게 분석 할 수 있다.
(1). j < w [i] 의 경우 가방 용량 이 부족 하여 제 i 아 이 템 을 내 려 놓 을 수 있 습 니 다. 가지 지 않 기로 선택 할 수 밖 에 없습니다.
m[ i ][ j ] = m[ i-1 ][ j ]
(2). j > = w [i] 의 경우 가방 용량 이 i 번 째 아 이 템 을 내 려 놓 을 수 있 습 니 다. 이 아 이 템 을 가지 고 더 큰 가 치 를 얻 을 수 있 는 지 고려 해 야 합 니 다.
가 져 가면 m [i] [j] = m [i - 1] [j - w [i] + v [i].여기 m [i - 1] [j - w [i] 는 i - 1 개의 아 이 템 을 고려 한 것 으로 가방 용량 이 j - w [i] 일 때의 최대 가치 이자 i 번 째 아 이 템 에 w [i] 의 공간 을 비 운 셈 이다.
안 들 면 m [i] [j] = m [i - 1] [j], 동일 (1)
가 져 갈 지 말 지 는 당연히 이 두 가지 상황 을 비교 하 는 것 이 가장 가치 가 있다.
이로부터 상태 전이 방정식 을 얻 을 수 있다.
-
if(j>=w[i])
-
m[i][j]=max(m[i
-1][j],m[i
-1][j-w[i]]+v[i]);
-
else
-
m[i][j]=m[i
-1][j];
：0-1 。 0-1 ， m[i][j] j， i、i+1、……、n 0-1 。
v = {8, 10, 6, 3, 7, 2}，
w = {4, 6, 2, 2, 5, 1}，
C = 12 m[i][j] 。
0
1
2
3
4
5
6
7
8
9
10
11
12
1
0
0
0
8
8
8
8
8
8
8
8
8
2
0
0
0
8
8
10
10
10
10
18
18
18
3
0
6
6
8
8
14
14
16
16
18
18
24
4
0
6
6
9
9
14
14
17
17
19
19
24
5
0
6
6
9
9
14
14
17
17
19
21
24
6
2
6
8
9
11
14
16
17
19
19
21
24
( ， 0)
m[2][6], ， 6 ， 8， ， ， ， 10， 。m[2][6]=m[1][0]+10=0+10=10; ， m[6][12] ， C 。
-
#include
-
#include
-
using
namespace
std;
-
-
-
const
int N=
15;
-
-
-
int main()
-
{
-
int v[N]={
0,
8,
10,
6,
3,
7,
2};
-
int w[N]={
0,
4,
6,
2,
2,
5,
1};
-
-
-
int m[N][N];
-
int n=
6,c=
12;
-
memset(m,
0,
sizeof(m));
-
for(
int i=
1;i<=n;i++)
-
{
-
for(
int j=
1;j<=c;j++)
-
{
-
if(j>=w[i])
-
m[i][j]=max(m[i
-1][j],m[i
-1][j-w[i]]+v[i]);
-
-
-
else
-
m[i][j]=m[i
-1][j];
-
}
-
}
-
-
-
for(
int i=
1;i<=n;i++)
-
{
-
for(
int j=
1;j<=c;j++)
-
{
-
cout<
' ';
-
}
-
cout<<
endl;
-
}
-
-
-
return
0;
-
}
， ， 。
x[ ] ，x[i]=0 ，x[i]=1 。
m[n][c] ， m[n][c]=m[n-1][c] , n ， x[n]=0 ; x[n]=1。 x[n]=0 ， x[n-1][c] ； x[n]=1 ， x[n-1][c-w[i]] 。 ， 。（ ， 。。）
-
void traceback()
-
{
-
for(
int i=n;i>
1;i--)
-
{
-
if(m[i][c]==m[i
-1][c])
-
x[i]=
0;
-
else
-
{
-
x[i]=
1;
-
c-=w[i];
-
}
-
}
-
x[
1]=(m[
1][c]>
0)?
1:
0;
-
}
：
A、B、C、D ， Wk Vk ， 30 ， ？
Project
Wk
Vk
A
15
12
B
10
8
C
12
9
D
8
5
-
#include
-
#include
-
using
namespace
std;
-
-
const
int N=
150;
-
-
int v[N]={
0,
12,
8,
9,
5};
-
int w[N]={
0,
15,
10,
12,
8};
-
int x[N];
-
int m[N][N];
-
int c=
30;
-
int n=
4;
-
void traceback()
-
{
-
for(
int i=n;i>
1;i--)
-
{
-
if(m[i][c]==m[i
-1][c])
-
x[i]=
0;
-
else
-
{
-
x[i]=
1;
-
c-=w[i];
-
}
-
}
-
x[
1]=(m[
1][c]>
0)?
1:
0;
-
}
-
-
int main()
-
{
-
-
-
memset(m,
0,
sizeof(m));
-
for(
int i=
1;i<=n;i++)
-
{
-
for(
int j=
1;j<=c;j++)
-
{
-
if(j>=w[i])
-
m[i][j]=max(m[i
-1][j],m[i
-1][j-w[i]]+v[i]);
-
-
else
-
m[i][j]=m[i
-1][j];
-
}
-
}
/*
-
for(int i=1;i<=6;i++)
-
{
-
for(int j=1;j<=c;j++)
-
{
-
cout<
-
}
-
cout<
-
}
-
*/
-
traceback();
-
for(
int i=
1;i<=n;i++)
-
cout<
-
return
0;
-
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
nginx: [emerg] getpwnam ("ww") failed 오류 처리 방법해결 방안 nginx. conf 에서 user nobody 의 주석 을 지 워 도 됩 니 다. 해결 방안 nginx 라 는 사용 자 를 만 들 지 않 았 기 때문에 서버 시스템 에 nginx 사용자 그룹 과 사용자 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
