洛谷：P1049 装箱问题

//P1049

#include<iostream>

#include<algorithm>

#include<cmath>

using namespace std;

int map[20000][50],V,n,input[50],lest;

//图表

int max(int a,int b){return a>b?a:b;}

int f(int xx,int yy){

    if(xx<=0 || yy<0)return 0;//如果在此范围内为0

    else{

        if(map[yy][xx]!=0)return map[yy][xx]; 

        int temp=xx-input[yy];//目前背包是否可容下当前物品

        if(temp>=0){//可以的话

            temp=f(xx-input[yy],yy-1)+input[yy];

            //计算装这个的话最大是多少

            if(temp>V)temp=0;//不知道为何还得再加个超重检测

        }else{temp=0;}

        int temp1=max(f(xx,yy-1),temp);

        

        return map[yy][xx]=temp1;

        //对比装不装的结果

    }

}

int main(){

    int i;

    cin>>V>>n;

    for(i=0;i<n;i++)cin>>input[i];

    cout<<V-f(V,n-1)<<endl;

    if(0){//输出建立的表格

        cout<<" ";

        for(i=0;i<V;i++)cout<<i+1<<" ";

        cout<<endl;

        

        for(i=0;i<n;i++){

            cout<<input[i]<<" ";

            for(int xx=1;xx<=V;xx++){

                cout<<map[i][xx]<<" ";

            }

            cout<<endl;

        }

    }

    return 0;

}

地址：https://www.luogu.com.cn/problem/P1049