装箱问题的解法之一

2008-11-01 11:56  

#include<iostream>
using namespace std;

int main(void){
    int vL,n,vol[40];
    int f[20010];
    int i,j;
   
    cin>>vL>>n;
    for(i=1;i<=n;i++)
        cin>>vol[i];
   
    memset(f,0,sizeof(f));
    f[0] = true;
   
    for(i=1;i<=n;i++)
        for(j=vL-vol[i];j>=0;j--)
            f[j+vol[i] ] = f[j]||f[j+vol[i] ];
   
    i = vL;
    while(!f[i]) i--;
   
    cout<<vL-i;
   
    system("pause");
    return 0;
}