题目描述

有一个箱子容量为V（正整数，），同时有n个物品（），每个物品有一个体积（正整数）。
要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

输入描述:

1个整数，表示箱子容量
1个整数，表示有n个物品
接下来n行，分别表示这n个物品的各自体积

输出描述:

1个整数，表示箱子剩余空间。

示例1

输入
24
6
8
3
12
7
9
7
输出
0

解答

这题经典的01背包。 
动规。 
设计状态表示前n个物体放在V中的最大体积是多少。 
所以代码如下： 
#include<bits/stdc++.h>
using namespace std;
int f[35][20003];
int dp(int* v,int V,int n){
    if(f[n][V]>0){
        return f[n][V];
    }
    if(n==0){
        return 0;
    }
    if(V>=v[n-1]){
        f[n][V]=max(dp(v,V,n-1),dp(v,V-v[n-1],n-1)+v[n-1]);
    }else{
        f[n][V]=dp(v,V,n-1);
    }
    return f[n][V];
}
int main(){
    int V,n;
    memset(f,-1,sizeof(f));
    scanf("%d%d",&V,&n);
    int v[n];
    for(int i=0;i<n;i++){
        scanf("%d",&v[i]);
    }
    printf("%d",V-dp(v,V,n));             //1
    return 0;
}
1处：这里要注意一下，我们求出的动规结果是占用体积最大值，所以要拿总体积减一下。

来源： cggwz