동적 계획 초보 (01 가방, 완전 가방, 다 중 가방)
11423 단어 알고리즘
01 가방
용적 이 c 인 가방 을 정 하고 n 개의 무게 가 wi 이 고 가치 가 vi 인 물 체 를 포장 하여 포장 할 수 있 는 물체 의 최대 가 치 를 구 합 니 다.예 를 들 어 n = 3, c = 30, W [] = {16, 15, 15}, v = {45, 25, 25} 일 때 담 을 수 있 는 것 은 뒤의 두 물체 이 고 최대 가 치 는 50 이다.주어진 세 물체 의 경우 마지막 가방 에 나타 날 수도 있 고 가방 에 나타 나 지 않 을 수도 있다.물체 가 마지막 가방 에 나타 나 는 지 여 부 를 0 과 1 의 변수 로 표시 할 수 있다.하나의 물 체 를 하나의 전체 로 보면 모든 물체 가 가방 에 나타 나 는 것 은 하나의 길이 가 n 이 고 0 과 1 로 구 성 된 꼬치 로 표시 할 수 있다.분명히 모두 00... 00 에서 11.11 의 2 ^ n 가지 상황 이 존재 한다.00... 00 에서 11. 11 까지 이 문자열 을 10 진수 의 2 진법 표시 로 본다 면 10 진수 가 0 에서 2 ^ n - 1 입 니 다.이러한 전환 을 통 해 0 에서 2 ^ n - 1 로 순환 하 는 변 수 를 이용 하여 모든 물체 가 가방 에 나타 나 는 형 태 를 나타 내 고 이 를 n 길이 의 바 이 너 리 로 전환 할 수 있 으 며 해당 하 는 비트 의 수치 (0 과 1) 는 해당 하 는 물체 가 가방 에 나타 나 는 지 여 부 를 나타 낸다.이 사상 을 바탕 으로 디자인 된 절 차 는 다음 과 같다.
#include
#include
#define n 3
#define c 30
int w[n]={16,15,15};
int v[n]={45,25,25};
int main()
{
int num,temp;
int i;
int tempvalue, tempweight;
int maxvalue=0;
for(num=0;nummaxvalue)
maxvalue=tempvalue;
}
printf("%d
",maxvalue);
return 0;
}
이 코드 를 보고 01 가방 이 무엇 인지 대체적으로 알 게 되 었 을 것 이 라 고 믿 습 니 다. 그러나 이런 방법 은 현실 상황 에서 실 용적 이지 않 습 니 다. 물체 의 개수 가 많 을 때 물체 의 모든 배치 상황 을 일일이 열거 하면 계 산 량 이 상당히 커 질 것 입 니 다. 여기 서 01 가방 이 무엇 인지 이해 하 게 만 들 기 때 문 입 니 다.
그 다음 에 우 리 는 동태 계획 처리 01 가방 을 말한다. 동태 계획 에서 01 가방 은 한 층 한 층 가장 좋 은 과정 이다. 모든 물품 은 두 가지 상태 만 놓 을 수 있 기 때문에 그의 상태 전이 방정식 은: dp[i][v]=max{dp[i-1][v],dp[i-1][v-cc[i]]+ww[i]}；
상태 전이 방정식 을 어떻게 이해 해 야 합 니까? 그 중에서 dp [i] [v] 메모리 에 놓 인 값 은 가방 안의 물체 의 가 치 를 나타 내 고 dp [i] [v] 중의 i, v 는 각각 i 번 째 물체 와 가방 의 용량 이 v 임 을 나타 냅 니 다.그래서 방정식 은 간단 해 졌 다.둘 중 큰 경 우 를 선택한다.앞에서 말 했 듯 이 이 과정 은 층 층 이 가장 좋 은 것 이다. 즉, i 번 째 물 체 를 놓 을 때 i - 1 번 물체 가 가장 좋 은 상황 이기 때문에 i 번 째 물 체 를 놓 을 때 앞 i - 1 번 물체 의 기초 위 에서 놓 을 지 여 부 를 선택 하 는 것 이다.
상태 전이 방정식 을 알 겠 습 니 다. 몇 가지 문 제 를 보 겠 습 니 다.
HDU2602 http://acm.hdu.edu.cn/showproblem.php?pid=2602
제목 의 대의: 몇 년 전, 테 디 의 고향 에 '뼈 수집가' 라 는 남자 가 있 었 습 니 다.이 남 자 는 여러 가지 뼈 를 수집 하 는 것 을 좋아 합 니 다. 예 를 들 어 개, 소, 그 도 무덤 에 갔습니다. 뼈 수집 자 는 큰 자루 V 가 있 습 니 다. 그의 수집 여행 에는 뼈 가 많 습 니 다. 분명 한 것 은 서로 다른 뼈 가 서로 다른 가치 와 부 피 를 가지 고 있 습 니 다. 지금 은 그의 여행 중의 모든 뼈의 가 치 를 제시 합 니 다. 뼈 수집 기 가 얻 을 수 있 는 총액 의 최대 치 를 계산 할 수 있 습 니까?
이것 은 분명히 01 배낭 문제 이다.
AC 코드:
#include
#include
#include
using namespace std;
int dp[1100][1100];
int main (){
int T;
scanf ("%d",&T);
while(T--){
int N,V;
int WW[1100];
int VV[1100];
scanf ("%d%d",&N,&V);
memset(dp,0,sizeof(dp));
for (int i=1;i<=N;i++){
scanf ("%d",&VV[i]);
}
for (int i=1;i<=N;i++){
scanf ("%d",&WW[i]);
}
//
for (int i=1;i<=N;i++){
for (int j=0;j<=V;j++){
if(WW[i]<=j){// i
dp[i][j]=max(dp[i-1][j],dp[i-1][j-WW[i]]+VV[i]);
}
else{// i i-1
dp[i][j]=dp[i-1][j];
}
}
}
//
/*for (int i=0;i<=N;i++){
for (int j=0;j<=V;j++){
printf ("%5d",dp[i][j]);
}
putchar('
');
} */
printf ("%d
",dp[N][V]);
}
return 0;
}
HDU1203
http://acm.hdu.edu.cn/showproblem.php?pid=1203
여기에 약간의 수학 기 교 를 사용한다. 최소한 의 오 피 스 를 받 을 수 있 는 가장 큰 확률 을 구 하 는 것 도 오 피 스 를 구 해도 받 을 수 없 는 가장 작은 확률 이 라 고 할 수 있다.
AC 코드:
#include
#include
#include
using namespace std;
float dp[100010];
int mm[100010];
float ff[100010];
int main (){
int n,m;
while (scanf ("%d%d",&n,&m)&&(n||m)){
for (int i=0;i=mm[i];j--){//
dp[j]=min(dp[j],dp[j-mm[i]]*ff[i]);
}
}
printf ("%.1f%%
",(1-dp[n])*100);
}
return 0;
} HDU1864 http://acm.hdu.edu.cn/showproblem.php?pid=1864
심사 문제 가 매우 중요 하 다. 데이터 처 리 는 매우 중요 한 문제 에서 소수 자릿수 를 제시 하기 때문에 우 리 는 소 수 를 정수 로 바 꾸 고 01 가방 을 풀 수 있다.
AC 코드:
#include
#include
#include
using namespace std;
int dp[3000001];
int cost[33];
int num[3];
int main (){
int N;
float Q;
int Q2;
while (scanf ("%f%d",&Q,&N)&&N){
Q2=(int)(Q*100);
int len=0;
memset(dp,0,sizeof(dp));
memset(cost,0,sizeof(cost));
while (N--){
int m;
scanf ("%d",&m);
float x;
memset(num,0,sizeof(num));
int flag=1;
while (m--){
char o;
scanf (" %c:%f",&o,&x);
// A B C 600
if (o=='A'&&x<=600){
num[0]+=(int)(x*100);
}
else if (o=='B'&&x<=600){
num[1]+=(int)(x*100);
}
else if (o=='C'&&x<=600){
num[2]+=(int)(x*100);
}
else {//
flag=0;
}
}
if (num[0]+num[1]+num[2]<=1000*100&&num[0]<=600*100&&num[1]<=600*100&&num[2]<=600*100&&flag){
cost[len++]=num[0]+num[1]+num[2];
}
}
for (int i=0;i=cost[i];j--){
dp[j]=max(dp[j],dp[j-cost[i]]+cost[i]);
}
}
printf ("%.2f
",dp[Q2]/100.0);
}
return 0;
} HDU2955 http://acm.hdu.edu.cn/showproblem.php?pid=2955
제목: 한 강도 가 몇 개의 은행 에 가서 훔 치 려 고 하 는데 그 는 돈 을 더 투자 하고 싶 을 뿐만 아니 라 잡 히 지 않 으 려 고 한다.각 은행 의 돈 수 와 잡 힐 확률, 그리고 강도 가 용인 할 수 있 는 최대 잡 힐 확률 을 알 고 있다.그 에 게 가장 많 게 는 얼 마 를 훔 칠 수 있 습 니까?
얼핏 보면 01 가방 제목 인 데 안에 문제 가 있어 요. 가방 의 용량 은 소수 이다. 이 건 곤란 합 니 다.그럼 우 린 어 떡 하지?사실 01 가방 변형 문제 입 니 다. 우 리 는 빼 앗 은 총 돈 수 를 가방 의 용량 으로 할 수 있다. 그리고 안 잡 힐 확률 을 구하 세 요. 맞아요. 안 잡 힐 확률 이에 요. 구 한 후에 다시 한 번 배열 을 옮 겨 다 니 며 첫 번 째 는 등 보다 크 고 잡 히 지 않 을 확률 을 찾 습 니 다. 수출 금액 만 있 으 면 된다.
AC 코드:
#include
#include
#include
using namespace std;
float dp[10110];
int ww[110];
float vv[110];
int main (){
int t;
scanf ("%d",&t);
while (t--){
float v;
int n;
int sum=0;
scanf ("%f%d",&v,&n);
v=1-v;
for (int i=0;i=ww[i];j--){
dp[j]=max(dp[j],dp[j-ww[i]]*vv[i]);
}
}
for (int i=sum;i>=0;i--){//
if(dp[i]>=v){
printf ("%d
",i);
break;
}
}
}
return 0;
}
완전 가방
완전 가방 과 01 가방 의 차 이 는 무 종 물체 가 무한 개 라 는 것 이다.
상태 전이 방정식 은 dp [i] [v] = max {dp [i - 1] [v - k * c [i]] + k * w [i] | 0 < = k < = n [i]} 이다.
여기 와 01 가방 의 차 이 는 안쪽 순환 순서 입 니 다.
지금 중요 한 것 은 왜 완전히 가방 을 이렇게 쓸 수 있 느 냐 는 것 이다.다음 에 우리 가 먼저 기억 해 보 자. 01 가방 역순 의 원인 은?max 의 두 가지 가 전 상태 값 이기 위해 서 입 니 다.그럼 여기, 우 리 는 순서대로 쓰 겠 습 니 다. 여기 max 의 두 가 지 는 당연히 현재 상태의 값 입 니 다. 왜 요?가방 마다 무한 하기 때문이다.우리 가 i 를 1 에서 N 으로 순환 할 때 f [v] 는 용량 이 v 가 앞의 i 가지 가방 에서 얻 은 가 치 를 나타 낸다. 여기 서 우리 가 추가 해 야 할 것 은 앞의 가방 이 아니 라 현재 가방 이다.그래서 우리 가 고려 해 야 할 것 은 당연히 현재 상태 다.
HDU1114 http://acm.hdu.edu.cn/showproblem.php?pid=1114
제목: 어떤 사람 은 저금통 (동전 저장) 이 있 는데 비 어 있 을 때 E 가 무 겁 고 돈 이 가득 차 면 F 가 무 겁 습 니 다.지금 그 는 항 아 리 를 돈 으로 가득 채 워 동전 의 종류 와 무 게 를 주 고 저금통 이 적어도 얼 마 를 저축 할 수 있 는 지 계산 했다.
완전 가방 최소 화
AC 코드:
#include
#include
#include
using namespace std;
int dp[10100];
int vv[510];
int ww[510];
int main (){
const int maxinf=0x3f3f3f3f;
int t;
scanf ("%d",&t);
while (t--){
int low,hight;
scanf("%d%d",&low,&hight);
int weight=hight-low;
int n;
scanf ("%d",&n);
for (int i=0;i HDU1248 http://acm.hdu.edu.cn/showproblem.php?pid=1248
AC 코드:
#include
#include
#include
using namespace std;
int dp[10010];
int vv[3]={150,200,350};
int main (){
int T;
scanf ("%d",&T);
while (T--){
int m;
scanf ("%d",&m);
memset(dp,0,sizeof(dp));
for (int i=0;i<3;i++){
for (int j=vv[i];j<=m;j++){
dp[j]=max(dp[j],dp[j-vv[i]]+vv[i]);
}
}
printf ("%d
",m-dp[m]);
}
return 0;
} 멀 티 백 팩
다 중 가방 과 01 가방 과 완전 가방 의 차 이 는 각 물체 의 개수 가 제한 되 어 있다 는 것 이다.
저희 가 01 백 팩 으로 볼 수 있어 요. 그 사상 은 n 개의 물체 X 를 n 개의 같은 독립 물체 로 보 는 것 이다.
HDU2191 http://acm.hdu.edu.cn/showproblem.php?pid=2191
AC 코드:
#include
#include
#include
using namespace std;
int dp[110];
int vv[20020];
int ww[20020];
int main (){
int t;
scanf ("%d",&t);
while (t--){
int n,m;
scanf ("%d%d",&n,&m);
int len=0;
while (m--){
int p,h,c;
scanf ("%d%d%d",&p,&h,&c);
while (c--){
vv[len]=p;
ww[len]=h;
len++;
}
}
memset(dp,0,sizeof(dp));
for (int i=0;i=vv[i];j--){
dp[j]=max(dp[j],dp[j-vv[i]]+ww[i]);
}
}
printf ("%d
",dp[n]);
}
return 0;
} 이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
【Codility Lesson3】FrogJmpA small frog wants to get to the other side of the road. The frog is currently located at position X and wants to get to...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
