C++ 解决背包问题（动态规划）

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

输入格式

　　第一行为一个整数，表示箱子容量；
　　第二行为一个整数，表示有n个物品；
　　接下来n行，每行一个整数表示这n个物品的各自体积。

输出格式

　　一个整数，表示箱子剩余空间。
　　样例输入
　　24
　　6
　　8
　　3
　　12
　　7
　　9
　　7

样例输出

0

#include "iostream"
#include "vector"
using namespace std;
bool findinv(int *a,int i,int n)
{
    for (int j = 0; j <n ; ++j) {
        if(i==a[j])
        {
            return true;
        }
    }
    return false;
}
int main()
{
//    输入处理
    int v;
    cin>>v;
    int n;
    cin>>n;
    int a[n];
    for (int i = 0; i < n; ++i) {
        cin>>a[n];
    }

//    分别求出每一个容量的最优解
    vector<int> vi;
//    容量为0的默认最优解为0
    vi.push_back(0);
//    分别从1开始到v大小的容量
    for (int i = 1; i <= v; ++i) {
        if(findinv(a,i,n))
        {
//            如果有这个物品，就直接存放0
            vi.push_back(0);
        }
        else
        {
            vi.push_back(i);
//            进行计算i容量大小的最优解
            for (int l = 0,n=vi.size()-2; l <= n; ++l,n--) {
                if(vi[l]+vi[n]<vi[i])
                {
                    vi[i]=vi[l]+vi[n];
                }
            }
        }
    }
    cout<<vi[vi.size()-1]<<endl;
    return 0;
}