01 背包 状态转移方程 dp[j] = max{dp[j], 1 - (1 - dp[j - cost[i]]) * (1 - val[i]))};
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<iomanip> 5 #define mem(a) memset(a, 0, sizeof(a)) 6 using namespace std; 7 const int maxn = 10050; 8 double dp[maxn]; 9 double value[maxn]; int cost[maxn]; 10 int main() 11 { 12 int v, n; 13 while(cin >> v >> n && (v || n)) { 14 for(int i = 1 ; i <= n ; i++) 15 cin >> cost[i] >> value[i]; 16 mem(dp); 17 for(int i = 1 ; i <= n ; i++) 18 for(int j = v ; j >= cost[i] ; j--) 19 dp[j] = max(dp[j], 1 - ((1 - dp[j - cost[i]]) * (1 - value[i]))); 20 cout << setiosflags(ios::fixed) << setprecision(1) << 100 * dp[v] << "%" << endl; 21 } 22 return 0; 23 }