外卖小哥的保温箱

#include <bits/stdc++.h>
 
using namespace std;
 
typedef struct {
    int x, y;    //x为箱子个数，y表示选的这些箱子种原有的保温箱的个数
}mytype;
 
int main() {
    int n;
    cin >> n;
    int a[n], b[n], w = 0, ori_w = 0;
    for(auto &e : a) {cin >> e; ori_w += e;}
    for(auto &e : b) {cin >> e; w += e;} 
     
    mytype f[n+1][w+1];//f[i][j]表示在前i个箱子中选择f[i][j].x个箱子拼成j容量的容积，且f[i][j].y为选的这x保温箱的原有个数
    f[0][0] = {0, 0};    //边界条件
    for(int j = 1; j<=w; ++j) f[0][j] = {INT_MAX, 0};    //用无穷大表示拼不出
     
/*
*对于状态f[i][j]，即当前要在前i个箱子中选若干个箱子，使得能拼成容积为j的大箱子，对于第i个箱子，我们总共有两种选择，但是
*对于任何一种选择，我们都要得到最小的箱子个数，并且在确定箱子个数的同时还得保证这些箱子里原有保温瓶尽量的多，即移动
*的开销就会越小
*1）方案1:不选第i个，则f[i][j] = f[i-1][j]则要在前i-1个箱子里选
*2）方案2：选第i个，则还需在前i-1个里选择若干个箱子拼成 j-b[i-1]，若f[i-1][j].x > f[i-1][j-b[i-1]].x+1&nbs***bsp;          f[i-1][j].x == f[i-1][j-b[i-1]].x+1 && f[i-1][j-b[i-1]].y > f[i-1][j].y 
*           都有 f[i][j] = {f[i-1][j-b[i-1]].x+1, f[i-1][j-b[i-1]].y + a[i-1] }；
*/
    for(int i = 1; i<=n; ++i) {
        for(int j = 0; j<=w; ++j) {
            //不选箱子i
            f[i][j] = f[i-1][j];
            if(j>=b[i-1] && f[i-1][j-b[i-1]].x != INT_MAX) {    //前i-1个箱子得拼的成j-b[i-1]
                if(f[i][j].x > f[i-1][j-b[i-1]].x+1) 
                    f[i][j] = {f[i-1][j-b[i-1]].x+1, f[i-1][j-b[i-1]].y + a[i-1]};
                else if(f[i][j].x == f[i-1][j-b[i-1]].x + 1) {
                    if(f[i][j].y < f[i-1][j-b[i-1]].y + a[i-1])
                        f[i][j] = {f[i-1][j-b[i-1]].x+1, f[i-1][j-b[i-1]].y + a[i-1]};
                }
            }
        }
    }
     
    //现在只需选择能容纳ori_w所用最少箱子的那个f[n][j]
    mytype ans = {INT_MAX, 0};
    for(int j = ori_w; j<=w; ++j) {
        if(f[n][j].x != INT_MAX) {
            if(ans.x > f[n][j].x)
                ans = f[n][j];
            else if(ans.x == f[n][j].x) {
                if(ans.y < f[n][j].y) ans = f[n][j];
            }
        }
    }
    cout << ans.x << " " << ori_w - ans.y << endl;
    return 0;
}

vector<int> movethings(vector<int> &things,vector<int> &package) {
    //用冒泡排序的方法进行排序
    for (int i = package.size()-1; i >0; i--)
    {
        for (int j = 0; j < i; j++)
        {
            if (package[j] > package[j+1]) {
                swap(package[i],package[j]);
                swap(things[i], things[j]);
            }
        }
    }
    int i=0, j=package.size()-1;
    int time = 0;
    //排序左边的货物搬移到右边
    while (i<j)
    {
        if ((things[i])>(package[j]-things[j])) {
            time = time + package[j] - things[j];
            things[i] = things[i] - (package[j] - things[j]);
            things[j] = package[j];
            j--;
        }
        else
        {
            time = time + things[i];
            things[j] = things[i] + things[j];
            things[i] = 0;
            i++;
        }
    }
    vector<int> v;
    v.push_back(time);
    v.push_back(package.size() - i);
    return v;
}

int main() {
    int n,temp;
    cin >> n;
    vector<int> things,package;
    for(int i=0;i<n;i++)
    {
        cin >> temp;
        things.push_back(temp);
    }
    for (int i = 0; i < n; i++)
    {
        cin >> temp;
        package.push_back(temp);
    }
    vector<int> v =movethings(things, package);
    cout<<v[1]<<" "<<v[0]<<endl;
}

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

map = {}
pick = []

for i in range(len(b)):
    map[b[i]] = i

sum = sum(a)         # 计数总共需要的容量
b.sort(reverse=True) # 按容量从大到小排列 贪心法 贪心策略 优先选容量最大的

i = 0
while sum > 0 and i < len(b): # 按容量从大到小选保温箱 
    sum -= b[i]
    pick.append(map[b[i]])    # 保存保温箱在的索引
    i += 1
need = 0
for i in range(len(a)):
    if i in pick:             # 遇到已选择的保温箱 跳过
        continue
    else:
        need += a[i]          # 没选这个保温箱 需要移动 加到need

print(need)                   # need 保存了所有需要移动的容量

#include<iostream>
#include<map>
using namespace std;
map<pair<int,int>,pair<int,int>> hash_map;
pair<int,int> solution(const int* a,const int* b,const int N,int n,int m){
    pair<int,int> nm=make_pair(n,m);
    if(hash_map.count(nm)){
        return hash_map[nm];
    }
    if(m<=0){
        hash_map[nm]=make_pair(0,0);
        return hash_map[nm];
    }
    if(n==1){
        if(b[0]>=m){
            hash_map[nm]=make_pair(1,a[0]);
        }else{
            hash_map[nm]=make_pair(-1,-1);
        }
        return hash_map[nm];
    }
    pair<int,int> last=solution(a,b,N,n-1,m);
    pair<int,int> last_=solution(a,b,N,n-1,m-b[n-1]);
    if(last.first==-1&&last_.first==-1){
        hash_map[nm]=last;
    }else if(last.first==-1){
        hash_map[nm]=make_pair(last_.first+1,last_.second+a[n-1]);
    }else if(last_.first==-1){
        hash_map[nm]=last;
    }else{
        if(last.first<last_.first+1){
            hash_map[nm]=last;
        }else if(last.first>last_.first+1){
            hash_map[nm]=make_pair(last_.first+1,last_.second+a[n-1]);
        }else{
            hash_map[nm]=make_pair(last.first,max(last.second,last_.second+a[n-1]));
        }
    }
    return hash_map[nm];
}
int main(){
    int n;
    cin>>n;
    int *a=new int[n],*b=new int[n];
    int m=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
        m+=a[i];
    }
    for(int i=0;i<n;i++){
        cin>>b[i];
    }
    pair<int,int> rs=solution(a,b,n,n,m);
    cout<<rs.first<<" "<<(m-rs.second)<<endl;
    return 0;
}