POJ 1252 유로 효율(BFS 또는 완전 가방)
http://poj.org/problem?id=1252
제목:
6 가지 화폐 가 있 는데 그들의 액면 가 는 각각 1,v2,v3,v4,v5,v6 이다.그리고 그들의 액면가 의 최대 치 는 100 보다 작다.최소 치 는 항상 1(바로 그 v1)이다.현재 의 문 제 는 가능 한 한 적은 6 가지 화폐 로 1 에서 100 의 모든 액면가 의 돈 을 구성 하 라 는 것 이다.이 100 개의 수 를 구성 하 는 데 평균 몇 개의 화폐 가 필요 하 냐 고 물 었 다.최대 몇 개의 화폐 가 필요 합 니까?
주의:여기 서 의 구성 은 더하기 뿐만 아니 라 상쇄 도 포함한다.즉,화폐 액면가 가 1,3,5,7,9,11 이 라 고 가정 할 때 구조 가 필요 하 다.그러면 1+3 을 사용 할 수 있 고 5-1 로 구 조 를 할 수 있 으 며 1+1+1+1 로 구 조 를 구성 할 수 있다.
분석:
해법 1: BFS 범위 우선 검색.
1-100 을 구성 해 야 하기 때문에 이 100 개의 수 는 우리 에 게 모든 숫자 에 최소 몇 개의 화폐 가 필요 하 냐 고 물 으 면 된다.또한 원래 의 화 폐 는 감법 연산 도 할 수 있 기 때문에 우 리 는 원래 6 가지 화 폐 를 바탕 으로 6 가지 화 폐 를 추가 했다.이 6 가지 새로운 화폐 면적 은 원래 6 가지 화폐 액면가 의 마이너스 이다.
우 리 는 dist[i]==x 로 하여 금 구조 면 가 를 i 돈 으로 최소 x 개의 화폐 가 필요 하 다 는 것 을 나타 낸다.
초기 값 dist 는 전체 INF 이 고 dist[0]=0 입 니 다.
그 후에 우 리 는 BFS 를 진행 하면 됩 니 다.대체적인 사상 은 바로 우리 가 u 점 에서 출발 하 는 것 입 니 다.만약 에 u 점 에서 특정한 점 v 까지 의 거리 가 v 점 의 원래 거리 보다 작다 면 우 리 는 v 점 의 더욱 좋 은 구조 방법 을 찾 았 습 니 다.그러면 v 점 으로 구 성 된 모든 다른 점 도 업데이트 해 야 하기 때문에 v 점 이 대열 에 들 어 갑 니 다.다음 에 v 점 을 꺼 내 서 BFS 를 진행 하면 v 점 으로 구 성 된 모든 다른 후계 노드 의 dist 값 을 업데이트 할 수 있 습 니 다.
대기 열 이 비어 있 을 때 구조 가 완료 되 었 음 을 설명 하고 통계 결 과 를 종료 하면 됩 니 다.
한 가지 주의해 야 할 것 이 있 습 니 다.매번+화폐의 액면 가 는 마이너스 가 될 수 있 기 때문에 우 리 는 100 액면가 안의 돈 만 구성 해 야 하 더 라 도 100 을 구성 하 는 과정 에서 100 을 초과 할 수 있 습 니 다.예 를 들 어 화폐 액면가 가 151 91 92 93 94 일 때구조 100 의 가장 좋 은 방법 은 51+51-1-1 이다.그러면 우 리 는 102 액면가 돈의 구조 dist[102]가 있어 야 dist[100]를 정확하게 출시 할 수 있다.
해법 2:두 번 완전 가방 DP.
액면 가 를 구성 하 는 돈 은 화폐 가 치 를 가감 해 야 하기 때문에 다음 과 같은 구조 에 대해
100=55+55-4-2 우 리 는 55+55 를 최대 지불 수량 으로 정의 할 수 있 습 니 다.-4-2 는 0 수 를 찾 고 100 은 최종 지불 수량 입 니 다.
사실 우 리 는 모든 위의 구조 과정 을 두 부분 으로 나 누 어도 무방 하 다.구조 최대 지불 수 와 거스름돈 이다.
첫 번 째 구조 최대 지불 수:(1 차 완전 가방 과정)
dp[i][j]==x 는 전 i 가지 화폐 로 얻 을 수 있 는 액면가 가 j 의 돈 일 때 최소 x 개의 화폐 가 필요 하 다 고 표시 합 니 다.
초기 값 dp 는 모두 INF(무한대),dp[0][0]=0 입 니 다.
상태 이동:dp[i][j]=min(dp[i-1][j],dp[i][j-val[i]]]+1)
전 자 는 i 번 째 화 폐 를 하나 도 사용 하지 않 는 다 고 밝 혔 고 후 자 는 적어도 1 번 째 i 번 째 화 폐 를 사용 하 겠 다 고 밝 혔 다.
최종 dp[n][0]부터 dp[n][maxn]까지 모두 우리 가 필요 로 하 는 데이터 입 니 다.그들 은 우리 가 증가 하고 감소 하지 않 을 때 최소 몇 개의 화폐 가 금전 액면가 에 도달 할 수 있 는 지 를 나타 냅 니 다.
두 번 째 단계 0 찾기:(다른 완전 가방 과정)
지난 단계 에 계승 한 dp 결과 에 따 르 면 우 리 는 지금 dp[i][j]==x 로 하여 금 결정 전 i 개 물품 을 결정 한 후에(i 번 째 물품 을 선택 하면 현재 화폐 가 가치 가 있 는 토대 에서 val[i]를 뺀 것 을 나타 낸다)금전 액면가 가 j 일 때 최소 x 개의 화폐 가 필요 하 다.
초기 값:이전 DP 의 결과.
상태 이동:dp[i][j-val[i]]=min(dp[i-1][j-val[i]]],dp[i][j]+1)
전 자 는 i 번 째 화폐 가 하나 도 줄 지 않 는 다 고 밝 혔 고 후 자 는 적어도 1 번 째 화 폐 를 줄 이 겠 다 고 밝 혔 다.
최종 dp[n][1]부터 dp[n][100]까지 모두 우리 가 필요 로 하 는 데이터 입 니 다.
프로그램 이 사용 하 는 스크롤 배열 이 므 로 dp 는[j]1 차원 만 있 습 니 다.
해법 3:12 가지 화폐 로 보고 1 회 완전 가방
또 6 개의 화 폐 를 12 개의 다른 화폐 로 직접 보고 완전 가방 을 만 들 수 있 습 니까?
네,하지만 화 폐 를 넣 는 것 과 화 폐 를 줄 이 는 것 은 전달 순서 가 다 릅 니 다.화 폐 를 넣 는 것 은 화폐 총액 이 작 을 때 부터 큰 것 으로 미 루 는 것 입 니 다.서로 다른 val[i]에 대해 서로 다른 처 리 를 하면 됩 니 다.
프로그램 중의 maxn 은 내 가 직접 테스트 한 것 이지 만 인터넷 에서 누군가가 이 maxn 의 범위 증명 을 제시 했다.
” 최대 지불 금액(예 를 들 어 인민폐 에서 49 를 지불 하면 50 을 먼저 지불 할 수 있 고 1 을 찾 으 면 50 을 최대 지불 금액 이 라 고 한다)은(100/val[1])*val[6]+100 보다 적 을 것 이다.이 값 에 도달 하면 최소 100/val[1]=100 을 찾 아야[1,100]의 범위 로 돌아 갈 수 있 기 때문에 직접 val[1]로 지불 하 는 것 이 낫다.
AC 코드 1:BFS 방법
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
#define INF 1e8
const int maxn=200+5;
int n=12;// 12
int val[12+5];//
int dist[maxn];
void BFS()
{
//
queue<int> Q;
for(int i=1;i<maxn;i++)
dist[i]=INF;
dist[0]=0;
Q.push(0);
//BFS 1-200 , dist[i]
while(!Q.empty())
{
int u=Q.front(); Q.pop();
for(int i=1;i<=n;i++)
{
int v=u+val[i];
if(v>=1 && v<maxn && dist[u]+1<dist[v] )
{
dist[v] = dist[u]+1;
Q.push(v);
}
}
}
// :sum ,max_step
int sum=0,max_step=0;
for(int i=1;i<=100;i++)
{
max_step = max(max_step,dist[i]);
sum += dist[i];
}
printf("%.2f %d
",sum/100.0,max_step);
// %.2lf , C++AC,G++WA.
}
int main()
{
int T; scanf("%d",&T);
while(T--)
{
for(int i=1;i<=6;i++)
scanf("%d",&val[i]);
for(int i=7;i<=n;i++)
val[i]=-val[i-6];
BFS();//
}
return 0;
}
AC 코드 2:완전 가방 2 회
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=2000+5;
int n=6; //
int val[7];//
int dp[maxn];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
//
for(int i=1;i<=6;i++)
scanf("%d",&val[i]);
//
for(int i=0;i<maxn;i++)
dp[i]=INF;
dp[0]=0;
// DP, dp[ ]
for(int i=1;i<=n;i++)
{
for(int j=val[i];j<maxn;j++)
dp[j]= min(dp[j], dp[j-val[i]]+1);
}
// DP, dp[ ]
for(int i=1;i<=n;i++)
{
for(int j=maxn-1;j>=val[i];j--)
dp[j-val[i]] = min(dp[j-val[i]], dp[j]+1);
}
//
int sum=0,max_val=0;
for(int i=1;i<=100;i++)
{
sum += dp[i];
max_val=max(max_val,dp[i]);
}
printf("%.2f %d
",sum/100.0,max_val);
}
}
AC 밴드 코드 3: 완전 가방
#include<cstring>
#include<cstdio>
#include<algorithm>
#define INF 1e9
using namespace std;
const int maxn=2000+5;
int n=12; //
int val[13];//
int dp[maxn+100];
int main()
{
int T;
scanf("%d",&T);
while(T--)
{
// , 12
for(int i=1;i<=6;i++)
{
scanf("%d",&val[i]);
val[i+6] = -val[i];
}
//
for(int i=0;i<maxn;i++)
dp[i]=INF;
dp[0]=0;
//
for(int i=1;i<=n;i++)
{
if(val[i]>0)
{
for(int j=val[i];j<maxn;j++)
dp[j]= min(dp[j], dp[j-val[i]]+1);
}
else if(val[i]<0)
{
int v = -val[i];
for(int j=maxn-1;j>=v;j--)
dp[j-v] = min(dp[j-v], dp[j]+1);
}
}
//
int sum=0,max_val=0;
for(int i=1;i<=100;i++)
{
sum += dp[i];
max_val=max(max_val,dp[i]);
}
printf("%.2f %d
",sum/100.0,max_val);
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
하나의 수조를 깊이가 가장 낮은 두 갈래 나무로 바꾸다문제 정의: Givena sorted(increasing order) array, write an algorithm to create abinary tree with minimal height. 생각: 이 문제는 비...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
