01 背包 状态转移方程 dp[j] = max{dp[j], 1 - (1 - dp[j - cost[i]]) * (1 - val[i]))};

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          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 }