1113. 装箱问题

while True:
    try:
        V = int(input())
        n = int(input())
        items = [int(i) for i in input().split()]
        res = [0]*(V+1)
        for i in range(n):
            for j in range(V, items[i]-1, -1):
                res[j] = max(res[j], res[j-items[i]]+items[i])
        print(V-res[V])
        input()  # 数据集里有蜜汁空行
    except:
        break

//状态:dp[i][j] 代表将前i个物品放入背包为j大小的最大值
#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

int a[32];
int dp[32][20010];

int main() {
    int v, n;
    while (cin >> v >> n) {
        memset(a, 0, sizeof(a));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= n; ++i) {
            cin >> a[i];
        }
        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= v; ++j) {
                if (j >= a[i]) {
                    dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - a[i]] + a[i]);
                }
                else {
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        int ans = v - dp[n][v];
        cout << ans << endl;
    }
    return 0;
}

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 100;
int a[N];
int n, v;
int _max;
void DFS(int index, int sum) {
    if (sum > v) {
        return;
    }
    if (index == n) {
        if (sum <= v && sum > _max) {
            _max = sum;
        }
        return;
    }
    DFS(index + 1, sum);
    DFS(index + 1, sum + a[index]);
}

int main() {
    while (cin >> v >> n) {
        fill(a, a + N, 0);
        _max = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }
        DFS(0, 0);
        int ans = v - _max;
        cout << ans << endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100;
int a[maxn];
int Max = 0;        //最大的体积; 
int V,n;

void dfs(int index,int sum) {   //index:当前选的下标，weight当前总重量 
    if(sum > V || index > n) return;
    if(sum > Max) Max = sum;        
    dfs(index+1,sum);       //不选当前 
    dfs(index+1,sum+a[index]);  ///选当前 
}

int main() {
    while(cin>>V>>n) {
        Max = 0;
        memset(a,0,sizeof(a));
        for(int i = 0;i < n;i++) cin>>a[i];
        dfs(0,0);//当前体积 
        cout<<V-Max<<endl;
    }
    return 0;
}

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

int main() {
    unsigned v, n;
    while (scanf("%u%u", &v, &n) ^ EOF) {
        unsigned vol[30];
        for (unsigned i = 0; i < n; ++i)
            scanf("%u", vol + i);
        vector<unsigned> dp(20001, 0);
        for (unsigned i = 0; i < n; ++i)
            for (unsigned j = v; j >= vol[i]; --j)
                if (j >= vol[i] && dp[j] < dp[j - vol[i]] + vol[i])
                    dp[j] = dp[j - vol[i]] + vol[i];
        printf("%u\n", v - dp[v]);
    }
}