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);
}
}