[NOIP2001]装箱问题（动态规划_01背包）

原题：https://ac.nowcoder.com/acm/contest/24213/1017

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <cmath>
#include <time.h>
#include <iomanip>
#include <cctype>
#include <string>   //https://ac.nowcoder.com/acm/contest/24213/1017
using namespace std;
typedef long long ll;
const ll Mod = 1e9 + 7;
//dp[i][j] 第i天，箱子总体积为j,是否存在此方案（0或1）
//若j>=w[i]   dp[i][j]=dp[i-1][j-w[i]] || dp[i-1][j]   *第i天可以取可以不取
//若j<w[i]    dp[i][j]=dp[i-1][j]       *第i天只能不取，否则会超过j 
int w[50];
bool dp[35][20005];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int v;cin>>v;
    int n;cin>>n;
    dp[0][0]=1;
    for(int i=1;i<=n;i++){
        cin>>w[i];
        for(int j=v;j>=0;j--){
            if(j>=w[i]) dp[i][j]=dp[i-1][j-w[i]]||dp[i-1][j];
            else dp[i][j]=dp[i-1][j];
        }
    }
    for(int i=v;i>=0;i--){//第n天从v往下找看有没有方案，总体积最接近v的可行方案，剩余体积最小（v-i）
        if(dp[n][i]){
            cout<<v-i<<endl;
            return 0;
        }
    }
    cout<<v<<endl;
    return 0;
}