01背包

问题描述：

现有 n 件物品，一个最大容量为 w 的背包。第 i 件物品重量为 wi ，价值为 vi 。
已知对于一件物品，你必须选择取或不取，且每件物品只能被取一次（这就是“0/1”的含义）。
求放置哪几件物品进背包，使得背包中物品价值最大(或是求最大价值是多少等衍生问题)。

思路：

设 ans[n,w] 为当背包容重量为 w ，有 1 到 n 件物品可以选择时的最大价值。 显然有：

1、如果决定取并且可以取第 n 件物品时，有 ans[n,w]=ans[n-1,w-w[n]]+v[n] (w>=w[n])
2、如果决定不取第 n 件物品时，有 ans[n,w]=ans[n-1,w]

所以，状态转移方程为：

ans[n,w]=max{ans[n-1,w-w[n]]+v[n],ans[n-1,w]}

边界条件是：

ans[n,0]=0,ans[0,w]=0

算法代码

program  one_zero_bag;
var      v,p,bag:array[0..1000]of longint;
         n,total,i,j:longint;
begin
         fillchar(bag,sizeof(bag),0);
         readln(n,total);
         for i:=1 to n do readln(v[i],p[i]);
         for i:=1 to n do
           for j:=total downto v[i] do
             if bag[j]<bag[j-v[i]]+p[i]
               then bag[j]:=bag[j-v[i]]+p[i];
         for i:=total downto 1 do
           if bag[i]<>0 then
             begin writeln(bag[i]);break;end;
end.

---

算法优化

上面的算法可以经过优化使得其空间复杂度降到$O \left (n \right)$,而且常数因子更小

注意到当解决ans[n,w]时只需要知道ans[n-1,i] (i=1,2,3....W)就可以了,所以可以通过维护一个一维的数组来求解ans[n,w]...

为了更有伪代码的风格,使用缩进而不是begin和end来标识一个子语句.

下面的代码没有经过debug或者make,而且仅仅是一般的背包问题的伪代码

   for j:=1 to n do
       for i:=m downto 0 do
           if (w[j]<=i)and(f[i-w[j]]+v[j]>f[i]) then
               f[i]:=f[i-w[j]]+v[j];

如何理解这段代码呢???

结论:在每进行一次第一行的循环节(就是2-4行)后,数组f中f[i]就是前j个物品在i时间时的最优解.

为什么?当代码尚未开始执行,a显然满足这样的性质,每次循环时我们用第j个物品尝试加入到原来i体积的方案中,
如果发现当前解更优,就更新a[i]中的值.(这里非正式地地运用了一下循环不变式).
要注意其中i的循还顺序,当解问题a(i,j)时,我们需要问题a(k,j-1)的解,其中k<=i,换言之,在上述代码
中,我们解决a[i]这一子问题的时候需要保证a[k](k<=i)的数据还是未更新过的数据.而第2行的m downto 0恰好满足这个要求.

在这个基础上,我们可以加上一个小优化,就好像下面的伪代码一样:

1   for j:=1 to n do
2       for i:=m downto w[j] do
3           if f[i-w[j]]+v[j]>f[i] then
4               f[i]:=f[i-w[j]]+v[j];

对于优化过的算法,显然的,它的时间复杂度并没有变得更优,因为新算法需要求解同样多的子问题.但是,在运行常数和空间复杂度的角度看,新算法无疑更为优秀.

---

如果问题要求物品的组合恰好填满指定的容量,只需在初始化时将f[i]赋值为-maxlongint即可

C++代码：

#include<iostream>
 
#define MAX_thing 1010
#define MAX_volume 1010
 
#define MAX( A, B ) ( A > B ? A : B )
 
using namespace std;
 
int ans[ MAX_thing ][ MAX_volume ]
 
int cost[ MAX_thing ], value[ MAX_thing ];
 
int main()
{
     int N, i, V, j;
     while( cin >> N >> V )
     {
          for( i=0; i<=N; i++ )
            for( j=0; j<=V; j++ ) 
                  ans[i][j] = 0; 
 
          for( i=1; i<=N; i++ )
             cin >> cost[i] >> value[i];
 
          for( i=1; i<=N; i++ )
          {
               for( j = cost[i] ; j <= V ; j++ )
               {
                    ans[i][j] = MAX( ans[i-1][j], ans[ i-1][j-cost[i]] + value[i] );
               } 
          }
          cout << ans[ N ][ V ] << endl;
     }
     return 0;
}
 
 
/*----------------------------------------------------------------------------------*/
 
/*----------------------------------------------------------------------------------*/
 
空间优化至O（V）的代码:
 
#include<iostream>
 
#define MAX_NUM 1010
 
#define MAX( A, B ) ( A > B ? A : B )
 
using namespace std;
 
int ans[ MAX_NUM ], cost[ MAX_NUM ], value[ MAX_NUM ];
 
int one_zero_pack( int cost, int value, int V )
{
    for( int i = V; i >= cost; i-- )
        ans[i] = MAX( ans[i], ans[ i-cost ] + value );
}
 
int main()
{
    int N,V,i;
 
    while( cin >> N >> V )
    {
       for( i=0; i<=V; i++ )  ans[i] = 0;
 
       for( i=0; i<N; i++ ) cin >> cost[i] >> value[i];
 
       for( i=0; i<N; i++ )  one_zero_pack( cost[i], value[i], V );
 
       cout << ans[ V ] << endl;
    }
    return 0;
}