/*
又是一个裸的0/1Orz
要使剩余体积最小
就是要尽量装满
然后总体积减去装掉的体积
QAQ
*/
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int a[40];
int V,n;
int f[20010];

int main()
{
    cin>>V>>n;
    for(int i=1;i<=n;i++)
        cin>>a[i];
    for(int i=1;i<=n;i++)
        for(int j=V;j>=a[i];j--)
            f[j]=max(f[j],f[j-a[i]]+a[i]);
    cout<<V-f[V];
    return 0;
}

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
using namespace std;
int a[33];
int f[33][20010];
int main()
{
    //freopen("box.in","r",stdin);
    //freopen("box.out","w",stdout);
    int v,n;
    cin>>v>>n;
    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])
            f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
            else
            f[i][j]=f[i-1][j];
        }
    cout<<v-f[n][v]<<endl;
    return 0;
}

弱化版的01背包
水过...

#include<bits/stdc++.h>
using namespace std;
int a[31],f[20001];
int main(){
    int n,m;
    scanf("%d%d",&m,&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        for(int j=m;j>=a[i];j--)
            f[j]=max(f[j],f[j-a[i]]+a[i]);
    printf("%d",m-f[m]);
    return 0;
}

第二道DP题(。・д・。)

#include<iostream>
using namespace std;
int a[35];
int f[35][20005];
int main()
{
    int v,n;
    cin>>v>>n;
    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])
        f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
        else
        f[i][j]=f[i-1][j];
    }
    cout<<v-f[n][v]<<endl;
    return 0;
}

#include<bits/stdc++.h>
using namespace std;

int dp[20001][20001],v,n,a[31];

int main()
{
cin>>v>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=v;j++)
{
dp[i][j]=dp[i-1][j];
if(a[i]<=j)
{
if(dp[i-1][j-a[i]]+a[i]>dp[i][j])
{
dp[i][j]=dp[i-1][j-a[i]]+a[i];
}
}
}
}
cout<<v-dp[n][v];
return 0;
}

那么多dp，我来发个搜索吧
普通的暴搜显然要炸，但本题中途相遇搜索可以通过。最大数据31ms
O(1.414^n * logn)
```c++
// ConsoleApplication1.cpp : 定义控制台应用程序的入口点。
//

#include <cstdio>
#include<set>
#include<cstdlib>
#include<algorithm>
using namespace std;

int v;
int t[30];
int n;
int k1, k2;
bool sel[30];
set<int> s;
void dfs1(int lim)
{
if (lim == k1)
{
int sum = 0;
for (int i = 0;i<k1;i++)
{
if (sel[i])sum += t[i];
}
if (sum == v)
{
putchar('0');
exit(0);
}
if (sum<v)
{
s.insert(sum);
}
}
else
{
sel[lim] = true;dfs1(lim + 1);
sel[lim] = false;dfs1(lim + 1);
}
}
int ans;
void dfs2(int lim)
{
if (lim == n)
{
int sum = 0;
for (int i = k1;i<n;i++)
if (sel[i])sum += t[i];
int maxm = v - sum;
if (maxm < 0)return;
if (s.count(maxm))
{
putchar('0');
exit(0);
}
set<int>::iterator i = s.insert(maxm).first;
if (i == s.begin())ans = min(ans, maxm);
else
{
i--;
int addup = *i;
ans = min(ans, maxm - addup);
i++;
s.erase(i);
}
}
else
{
sel[lim] = true;dfs2(lim + 1);
sel[lim] = false;dfs2(lim + 1);
}
}
int main()
{
scanf("%d%d", &v, &n);
for (int i = 0;i<n;i++)scanf("%d", t + i);
ans = v;
k1 = n / 2;
k2 = n - k1;
dfs1(0);
dfs2(k1);
printf("%d", ans);
}
```

写了这么久DP，发个最简的代码吧，这上面我不知道如何在include前面加#号，你们记得加上
include<iostream>
include<algorithm>
using namespace std;
int v, n;
int w[200001];
int dp[200001];
int main(){
cin >> v >> n;
for (int i = 0; i < n; i++)
{
cin >> w[i];
}
for (int i = 0; i < n; i++)
{
for (int j = v; j >= w[i]; j--){
dp[j] = max(dp[j], dp[j - w[i]] + w[i]);
}
}
cout << v - dp[v];
return 0;
}

#include <iostream>
using namespace std;
int a[40],f[20010];
int V,n;
int main()
{
cin>>V>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=V;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]+a[i]);
cout<<V-f[V]<<endl;
return 0;
}

#include<bits/stdc++.h>
using namespace std;
int v,n,f[20001],a[20001];
int main()
{
cin>>v>>n;
for(int i=1;i<=n;i++)
cin>>a[i];

for(int i=1;i<=n;i++)
for(int j=v;j>=1;j--)
if(j>=a[i])
f[j]=max(f[j],f[j-a[i]]+a[i]);
cout<<v-f[v]<<endl;
return 0;
}

#include<iostream>
using namespace std;
int a[40];
int V,n;
int f[20010];

int main()
{
cin>>V>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int i=1;i<=n;i++)
for(int j=V;j>=a[i];j--)
f[j]=max(f[j],f[j-a[i]]+a[i]);
cout<<V-f[V];
return 0;
}

01背包的变式

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

这道题看似是搜索，但是可以用背包做。

题目要求求出最小的剩余空间，也就是要求出最大的可装重量

这样，我们可以将一个物体的重量当作它的价值，进而将题目转变为一个基本的01背包问题：

有一个箱子容量为V（正整数，0＜＝V＜＝20000），同时有n个物品（0＜n＜＝30），每个物品有一个体积（正整数）和一个价值（等于体积）。

要求n个物品中，任取若干个装入箱内，使总价值最大。

对于每一个物体，都有两种状态：装 与不装

那么，对于任意重量m的最大价值 f (m) = max ( f ( m - w[i] ) + w[i], f (m) )（w为重量（即价值））

其中，f ( m - w[i] ) 指在装了物品i后，箱子的剩余容量能装的最大重量

f ( m - w[i] ) + w[i] 指在在装了物品i后，箱子能装的最大重量

程序如下：

#include<cstdio>
using namespace std;
int m,n;                m即箱子容量V
int f[20010];
int w[40];
int main(){
    int i,j;
    scanf("%d%d",&m,&n);
    for(i=1;i<=n;i++){
        scanf("%d",&w[i]);
    }
    for(i=1;i<=n;i++){
        for(j=m;j>=w[i];j--){                            注意：这里必须是从m到w[i]，否则一个物体会被多次装入箱子，见例1
            if(f[j]<f[j-w[i]]+w[i]){
                f[j]=f[j-w[i]]+w[i];
            }
        }
    }
    printf("%d\n",m-f[m]);
}

例1： 输入：

5 1 1 假如在遍历容量m时从小到大遍历，你会发现:

f (2) = f (2 - 1) + w[1] = f (1) +w[1] = 2
f (3) = ... = 3
f (4) = 4
f (5) = 5
最后的答案就是5-5=0，然而正解是5-1=4

#include <iostream>         //[2001普及组-D]装箱问题
#include <algorithm>        //01背包问题
using namespace std;
const int MAXW = 20002;

int main()
{
    int V, n, W[31];
    int dp[MAXW] = {0};
    cin >> V >> n;
    for (int i = 1; i <= n; i++)
        cin >> W[i];

    for (int i = 0; i <= n; i++)
        for (int j = V; j >= W[i]; j--)
            dp[j] = max(dp[j], dp[j - W[i]] + W[i]);


    cout << V - dp[V] << endl;

    return 0;
}
//前i个物品，
//dp[i][j] = max(dp[i - 1][j], dp[i][j - w[i]] + w[i]);

/*01背包的变式，费用=价值。*/
#include<iostream>
#include<cstdio>
using namespace std;
int dp[100005],a[100005],v,n,i,j;
int main()

{
scanf("%d%d",&v,&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=v;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
printf("%d\n",v-dp[v]);
return 0;
}

//01背包的变式，费用=价值。
#include<iostream>
#include<cstdio>
using namespace std;
int dp[100005],a[100005],v,n,i,j;
int main()

{
scanf("%d%d",&v,&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=v;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
printf("%d\n",v-dp[v]);
return 0;
}

//01背包的变式，费用=价值
AC代码：
#include<iostream>
#include<cstdio>
using namespace std;
int dp[100005],a[100005],v,n,i,j;
int main()

{
scanf("%d%d",&v,&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
for(i=1;i<=n;i++)
for(j=v;j>=a[i];j--)
dp[j]=max(dp[j],dp[j-a[i]]+a[i]);
printf("%d\n",v-dp[v]);
return 0;
}

c++代码
#include<bits/stdc++.h>
using namespace std;
int a[33];
bool f[33][20003];
int main(){
int v,n;
scanf("%d%d",&v,&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0][0]=1;
for(int i=1;i<=n;i++)
for(int j=0;j<=v;j++){
f[i][j]=f[i-1][j];
if(j>=a[i]) f[i][j]=f[i][j] || f[i-1][j-a[i]];
}
for(int i=v;i>=0;i--)
if(f[n][i]){
printf("%d",v-i);
return 0;
}
}

//（悄咪咪）这是个80分炒鸡水的做法，证明数据之水~

#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int a[31];
int ans[1000];
int main()
{
int v,n,v1=0;
cin>>v>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
sort(a+1,a+1+31);
for(int i=31;i>=1;)
{
if(a[i]<=v-v1)
{
v1+=a[i];
i--;
}
else if(a[i]>v-v1)
{
i--;
}

}
cout<<v-v1;
return 0;
}

普通背包问题加一个限制条件：
最优解不大于最大容量
大于则维持原样，不大于则按普通背包问题
```c++
#include <cstdio>
#include <iostream>

using std::max;

int main(void){
freopen("in.txt","r",stdin);
int n,maxv;
int v[500];
int f[50000]={0};
scanf("%d%d",&maxv,&n);
for(int i=1;i<=n;i++)
scanf("%d",&v[i]);

for(int i=1;i<=n;i++)
for(int j=maxv;j>=v[i];j--)
f[j]=f[j-v[i]]+v[i]>maxv?f[j]:max(f[j-v[i]]+v[i],f[j]);
printf("%d",maxv-f[maxv]);
return 0;
}
```

#include <iostream>
#include <math.h>
#include <stdlib.h>
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
const int N = 1005;
int v,n,f[N][N],w[N],ans = 0;
int main(){
scanf("%d%d",&v,&n);
for(int i = 1;i <= n;i ++){
scanf("%d",&w[i]);
}
for(int i = 1;i <= n;i ++){
for(int j = v;j >= 0;j --){
f[i][j] = j >= w[i] ? max(f[i - 1][j - w[i]] + w[i],f[i - 1][j]) : f[i - 1][j];
}
}
ans = v - f[n][v];
printf("%d",ans);
return 0;
}