装箱问题（pack.cpp）

【问题描述】有一个箱子容量为V（正整数，0<=V<=20000）,同时有n个物品（0<n<=30）,每个物品有一个体积（正整数）。

要求n个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。

【输入样例】

24

6

8

3

12

7

9

7

【输出样例】

0

样例说明：

24——表示箱子容量

6——表示n个物品

8——n行，分别表示n个物品的体积

312

7

9

7

方法一、使用二维数组f[i][j],表示前i个物品装入容量为j的箱子能获得的最大体积，

动态转移方程： f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);

#include <iostream>
using namespace std;

int f[31][20001];

int main()
{
 freopen("pack.in","r",stdin);
 freopen("pack.out","w",stdout);
 int V,n,i,j;
 cin>>V>>n;
 int a[n+1];
 for(i=1;i<=n;i++)
  cin>>a[i];
 for(i=1;i<=n;i++)
  for(j=1;j<=V;j++)
  {
   if(j<a[i])
    f[i][j]=f[i-1][j];
   else
    f[i][j]=max(f[i-1][j],f[i-1][j-a[i]]+a[i]);
  }
 cout<<V-f[n][V];
 while(1);
 return 0;
}

方法二、方法一虽好，但占用内存空间较大，改用一维数组f[j]：

仍表示前i个物品装箱能获得的最大体积。

#include <iostream>
using namespace std;

int f[20001];//f[j]表示前i个物品装入获得的最大体积
int main()
{
 freopen("pack.in","r",stdin);
 freopen("pack.out","w",stdout);
 int V,n,i,j;
 cin>>V>>n;
 int a[n+1];
 for(i=1;i<=n;i++)
  cin>>a[i];
 for(i=1;i<=n;i++)
 {
  for(j=V;j>=1;j--)
  {
   if(j<a[i]) f[j]=max(f[j-1],f[j]);//虽然f[j]总是大于f[j-1],但这一句为什么不能少？
   else f[j]=max(f[j],f[j-a[i]]+a[i]);
  }
 }
 cout<<V-f[V];

//while(1);
 return 0;
}

方法三、

#include <fstream>
using namespace std;

ifstream fin("pack.in");
ofstream fout("pack.out");

int f[20001];

int main()
{
 int v,n,a[31],i,j,d;
 fin>>v>>n;
 
  for(i=1;i<=n;i++)
   fin>>a[i];
  
   for(i=1;i<=n;i++)//对n种物品
   {
    for(j=v;j>0;j--)//j为剩余空间
     if(f[j]==1&&j+a[i]<=v)
      f[j+a[i]]=1;
      f[a[i]]=1;
  }

 d=v;
   
    while(d>0&&f[d]!=1)
        d--;
 
 fout<<v-d<<endl;
 fin.close();
 fout.close();
 return 0;
}
试问方法三中f[j]的含义是什么？