01背包

#include <bits/stdc++.h>
using namespace std;
int v , n , w[35] , f[20005];
int main()
{
    cin >> v >> n;
    for (int i = 1 ; i <= n ; i++) cin >> w[i];
    for (int i = 1 ; i <= n ; i++)
    {
        for (int j = v ; j >= w[i] ; j--)
        {
            f[j] = max(f[j] , f[j - w[i]] + w[i]);
        }
    }
    cout << v - f[v];
    return 0;
}

#include <iostream>
using namespace std;
int m, n, f[20000], w[40];
int main()
{
    cin >> m >> n;
    for (int i = 1; i <= n; i += 1)
    {
        cin >> w[i];
    }
    for (int i = 1; i <= n; i += 1)
    {
        for (int j = m; j >= w[i]; j -= 1)
        {
            if (f[j] < f[j - w[i]] + w[i])
            {
                f[j] = f[j - w[i]] + w[i];
            }
        }
    }
    cout<< m - f[m] << endl;
    return 0;
}//已AC