题解 | #外卖小哥的保温箱#

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    cin >> n;
    int sum_goods = 0;
    int sum_cap = 0;
    vector<int> goods(n,0);
    vector<int> cap(n,0);
    for(int i = 0;i < n; i++){
        cin >> goods[i];
        sum_goods += goods[i];
    }
    for(int i = 0;i < n ; i++){
        cin >> cap[i];
        sum_cap += cap[i];
    }
    vector<int> dp(sum_cap + 1, sum_cap);
    dp[0] = 0;
    vector<int> weight(sum_cap + 1, 0);

   for (int i = 0; i < n; i++) {
       for (int j = sum_cap; j > 0; j--) {
           int res = max(j - cap[i], 0);
           if (dp[j] < dp[res] + 1) continue;
           else if (dp[j] > dp[res] + 1) {
               dp[j] = dp[res] + 1;
               weight[j] = weight[res] + goods[i];
           } else {
               weight[j] = max(weight[j], weight[res] + goods[i]);
           }
        }
   }

    int k = sum_cap;
    int max_weight = 0;

    for(int i = sum_goods; i <= sum_cap; i++){
         if(dp[i] < k){
             k = dp[i];
             max_weight = weight[i];
         }
         else if(dp[i] == k){
             max_weight = max(max_weight,weight[i]);
         }
     }

    cout<< k << " " << sum_goods - max_weight <<endl;

    return 0;
}