심 플 한 백 팩 변형 HDU 1203, HDU 2955

오늘 계속 가방 을 쓰 고 있 었 는데 중간 에 멈 춰 서 셸 을 쓰 고 있 었 습 니 다.
계속 01 가방 만 들 고 있어 요.오늘 이 두 문제 비슷 한 가방 을 만 들 었 어 요.
먼저 HDU 1203 입 니 다.
Speakless 는 일찍부터 출국 하고 싶 었 습 니 다. 지금 은 필요 한 모든 시험 을 마 쳤 고 준비 해 야 할 자 료 를 모두 준 비 했 기 때문에 학교 에 지원 해 야 합 니 다.외국 의 어떤 대학 에 지원 하려 면 일정한 신청 비용 을 내야 하 는데, 이것 은 정말 놀랍다.Speakless 는 돈 이 얼마 없어 서 모두 n 만 달러 만 모 았 다.그 는 m 개 학교 에서 몇 가 지 를 선택 할 것 이다.학교 마다 신청 비용 a (만 달러) 가 다 르 고 Speakless 는 그 가 이 학교 offer 를 받 을 가능성 b 를 예측 했다.서로 다른 학교 간 에 offer 를 받 았 는 지 여 부 는 서로 영향 을 주지 않 는 다."I NEED A OFPER"라 고 그 가 소 리 쳤 다.이 불쌍 한 사람 을 도와 주세요. 계산 해 주세요. 그 는 적어도 하나의 offer 를 받 을 수 있 는 가장 큰 확률 을 얻 을 수 있 습 니 다.(Speakless 가 여러 학 교 를 선택 했다 면 어느 학교의 offer 를 받 아 도 된다).
몇 개의 조 의 데 이 터 를 입력 하면 각 조 의 데이터 의 첫 줄 은 두 개의 정수 n, m (0 < = n < = 100000, 0 < = m < 100000) 뒤의 m 줄 이 있 고 각 줄 은 두 개의 데이터 ai (정형) 가 있 으 며 bi (실 형) 는 각각 i 개 학교의 신청 비용 과 offer 를 받 을 수 있 는 확률 을 나타 낸다.입력 한 마지막 에 0 이 두 개 있 습 니 다.
각 그룹의 데 이 터 는 하나의 출력 에 대응 하여 Speakless 가 최소한 하나의 offer 를 얻 을 수 있 는 최대 확률 을 나타 낸다.백분 수로 소수점 뒤의 한 자리 까지 정확하게 표시 하 다.
input

10 3
4 0.1
4 0.2
5 0.3
0 0

output
4. 567913. 이 문 제 는 아주 간단 합 니 다. 가방 은 돈 이 고 dp 는 합격 하지 못 할 확률 입 니 다.
dp[j]=min(dp[j],dp[j-c[i]]*(1-p[i]));
다음 출력 은 (1 - min {dp [j]}) * 100 입 니 다.
요즘 C 와 C++ 에서 자주 교환 되 는 지 모 르 겠 어 요. 그래서 제 가 좀 헷 갈 렸 어 요.
마지막 에 C 로 썼어 요.

44.0%

나중에 다시 생각해 보 니 사실은 dp [j] = max (dp [j], 1 - (1 - dp [j - c [i]]) * (1 - p [i]) 를 사용 할 수 있 습 니 다.전이 방정식 으로 삼다
그래서 조금 고 쳤 어 요.

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
 * Compiler     : GCC  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
 * Encoding     : UTF8
 * Date         : 2014-03-08
 * All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/



#include <stdio.h>
#include <string.h>
double dp[10003];
int c[10003];
double p[10003];
double fmin(double a,double b){
    if(a<b) return a;
    return b;
}
int main(){
    int n,m,i,j;

    while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
          memset(dp,0,sizeof(dp));
          memset(c,0,sizeof(c));
          memset(p,0,sizeof(p));

          for(i=n;i>=0;i--)
              dp[i]=1;
          for(i=1;i<=m;i++){
              scanf("%d%lf",&c[i],&p[i]);
          }
          for(i=1;i<=m;i++)
             for(j=n;j>=c[i];j--){
                 dp[j]=fmin(dp[j],dp[j-c[i]]*(1-p[i])) ;

             }
             double res=1;
           for(i=n;i>=0;i--){

              if(dp[i]<res){

                 res=dp[i];
              }

           }
           res=1-res;
           res*=100;
         printf("%.1lf%%
",res);

    }



     return 0;
}

HDU 2955 에 대해 서 는 사실 저 는 먼저 HDU 2955 를 만 들 었 습 니 다.
이 가방 은 총 금화 수 입 니 다. 상태 이동 은
dp[i]=max(dp[i],dp[i-v[i]]*(1-p[i]))
마지막 으로 출력 할 때 dp [i] > 1 - p 의 i 를 찾 으 면 됩 니 다.
그 중에서 v [i] 는 모든 은행 이 가 져 간 금화 이 고 p [i] 는 잡 힐 확률 이다.p 는 총 확률 이다.
C 하나, C++ 하나 써 놨 어 요. 느낌 이 별로 안 좋 으 면 C++ 아무 거나 보 내 주세요.

/*******************************************************************************/
/* OS           : 3.2.0-58-generic #88-Ubuntu SMP Tue Dec 3 UTC 2013 GNU/Linux
 * Compiler     : GCC  4.6.3 (Ubuntu/Linaro 4.6.3-1ubuntu5)
 * Encoding     : UTF8
 * Date         : 2014-03-08
 * All Rights Reserved by yaolong.
*****************************************************************************/
/* Description: ***************************************************************
*****************************************************************************/
/* Analysis: ******************************************************************
*****************************************************************************/
/*****************************************************************************/



#include <stdio.h>
#include <string.h>
double dp[10003];
int c[10003];
double p[10003];
double fmax(double a,double b){
    if(a>b) return a;
    return b;
}
int main(){
    int n,m,i,j;

    while(scanf("%d%d",&n,&m)!=EOF&&(n||m)){
          memset(dp,0,sizeof(dp));
          memset(c,0,sizeof(c));
          memset(p,0,sizeof(p));


          for(i=1;i<=m;i++){
              scanf("%d%lf",&c[i],&p[i]);
          }
          for(i=1;i<=m;i++)
             for(j=n;j>=c[i];j--){
                 dp[j]=fmax(dp[j],1-(1-dp[j-c[i]])*(1-p[i])) ;

             }



         printf("%.1lf%%
",dp[n]*100);

    }



     return 0;
}

그래.