1203 I NEED A OFFER! 簡単な問題解決レポート

2413 ワード

01リュックの問題の変形問題、とても簡単で、以下は私のACコードです.初期化は、すべて1、すなわち100%の値を割り当てます.memset関数はだめですよ.
#include <iostream>

using namespace std;



const int MAX=10001;

int c[MAX];

double dp[MAX];

double v[MAX];



int main()

{

    int n,m,i,j;

    double t;

    while(cin>>n>>m && (n||m))

    {

        for(i=0;i<m;i++)

        {

            cin>>c[i]>>t;

            v[i]=1-t;

        }

        for(i=0;i<MAX;i++)

            dp[i]=1;

        for(i=0;i<m;i++)

            for(j=n;j>=c[i];j--)

                if(dp[j]>(t=dp[j-c[i]]*v[i]))

                    dp[j]=t;

        printf("%.1f%%
",(1-dp[n])*100); } }