하늘에서 떨어지다 피자

원제:zjnu 1192
제목:
피자 한 가지를 사면 다른 피자 쿠폰을 받을 수 있는데, 단위 면적의 피자를 어떻게 팔면 가격이 가장 적게 팔릴 수 있냐고 묻는다(한 개 두 개 사면 마음대로 살 수 있다)
해결:
만약 dp문제가 순서문제를 풀었다면, 돌려서 풀기가 매우 어려울 것이다
올바른 방법은 매거 상태로 이전의 상태에서 옮겨오는 것이다.그러나 누가 먼저 사고 누가 사야 할지 생각하면 잘못된 길을 걷게 된다
dp[i]는 상태가 i일 때 최소 비용을 표시한다.eg:피자 5개==29(11101)는 피자 1,3,4,5종을 샀을 때의 상태를 표시하고 상태 이동 방정식은 dp[i]=min(dp[i],dp[i-(1<이다.
코드:

#include
#include
#include
#include
#include
using namespace std;

double ans;
int n,k;
double p[20],s[20];
double c[20][20];

double dp[1<<16],siz[1<<16];

int main(){
    while(scanf("%d",&n),n){
        ans=2.14e9;
        memset(c,0,sizeof(c));
        memset(siz,0,sizeof(siz));
        memset(dp,127,sizeof(dp));
        for(int i=1;i<=n;i++){
            scanf("%lf%lf%d",p+i,s+i,&k);
            while(k--){
                int a,b;
                scanf("%d%d",&a,&b);
                c[i][a]=(100-b)*1.0/100.0;
            }
        }
        dp[0]=0;
        for(int i=1;i1<for(int j=1;j<=n;j++){
                int f=1;
                if((i&(1<1)))==0)continue;
                double w=p[j];
                for(int k=1;k<=n;k++){
                    if((i&(1<1)))==0)continue;
                    if(c[k][j]<1e-8)continue;
                    w*=c[k][j];
                }
                dp[i]=min(dp[i-(1<1))]+w,dp[i]);
                siz[i]=siz[i-(1<1))]+s[j];
            }
            //printf("dp[%d] is %.1lf,size is %.1f
",i,dp[i],siz[i]);
            ans=min(ans,dp[i]/siz[i]);
        }
        printf("%.4lf
",ans);
    }
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

01 가방 문제(DP 동적 계획)

n개의 무게와 가치가 각각 와이,vi인 물품이 있습니다.이 물품들 중에서 총 중량이 W를 초과하지 않는 물품을 골라 모든 선택 방안 중 가치 총화의 최대치를 구한다. 1<=n<=100 1<=wi,vi<=100 1<=...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

하늘에서 떨어지다 피자

좋은 웹페이지 즐겨찾기