动态规划 之 0-1背包问题

【背包问题】

现有n个物品，价值为
`$$
v_1,v_2....v_n
$$

重量为

w_1,w_2...w_n

现有一背包，容量为C。假设$ v_i $,$w_i$,C都是整数。求最优的装包方案，使得背包价值最大。

---

求解：

设最优解为

$I={I_1,I_2...I_k}$

$ I_k$ 属于 $I$ 表示第k个物品被装入背包

这时我们假设已知最优解，那么从最优解来看，对于$I_1$有：

• 如果$I_1$$不属于$I$，有{$I_1,I_2,...I_n$}在C上的最优解等价于{$I_2,I_3...I_n$}在C上的最优解
• 如果$I_1$属于$I$,有{$I_1,I_2,...In$}在C上的最优解C上的最优解等价于{$I_2,I_3...I_n$}在$C-w_1$上的最优解加上$v_1$

记m[i,c]表示{$I_i,I_{i+1},...I_n$}在c上的最优解,则有：

//这里主要是考虑第n个物品在c容量下装不装得下

m[i,c]=\begin{cases}
        i==n,&w_i<=c,&w_i\\
            &else &0\\
        i<n,& c<w_i,&m[i+1,c]\\
            &else&max\left( m[i+1,c],m[i+1,c-w_i]+v_i \right)
    \end{cases}

//python风格的伪代码
    if i==n:
        if w[i]<c:
            m[n][c]=w[i]
        else:
            m[n][c]=0
    elif c<w[i]:
        m[i][c]=m[i+1][c]
    else:
        if m[i+1][c]>m[i+1][c-w[i]]+v[i]:
            m[i][c]=m[i+1][c]
        else:
            m[i][c]=m[i+1][c-w[i]]+v[i]
        

实例演算

接下来根据公式来推出最优解：

//原始数据
    int v[]={0,6,3,5,4,6};
    int w[]={0,2,2,6,5,4};
    int C=10;
    int n=5;

i\c	1	2	3	4	5	6	7	8	9	10
1
2
3
4
5

当i==5,
$v_i=6$,$w_i=4$
得到

    m[n,c]=(w_i<c)?w_i:0

i\c	1	2	3	4	5	6	7	8	9	10
1
2
3
4
5	0	0	0	6	6	6	6	6	6	6

接下来i=4,$v_i=4$,$w_i=5$

    m[i,c]=max\left( m[i+1,c],m[i+1,c-w_i]+v_i \right)

i\c	1	2	3	4	5	6	7	8	9	10
1
2
3
4	0	0	0	0	6	6	6	6	10	10
5	0	0	0	6	6	6	6	6	6	6

依次向上，得到：

i\c	1	2	3	4	5	6	7	8	9	10
1	0	6	6	9	9	9	12	12	15	15
2	0	3	3	3	6	6	9	9	10	10
3	0	0	0	0	6	6	6	6	10	10
4	0	0	0	0	6	6	6	6	10	10
5	0	0	0	6	6	6	6	6	6	6

得到最优的分配方案，最大价值为15

对于最优解，如果它和它正下方的那个数值相等，则表示这个点没被选中。
如：m[3,6]=6下面是m[4,6]=6,所以i=3没被选中

---

代码：

/* 
 * 动态规划背包求解
 *  m[n,c]=(wi<c)?vn:0
 *  m[i,c]=Max{m[i+1,c],m[i+1,c-wi]+vi}
 * 
 */
int packet(int w[],int v[],int n,int C){
    int m[SIZE][SIZE]={{0}};

    for(int c=0;c<=C;++c){
        m[n][c]=(w[n]<=c)?v[n]:0;
    }

    for(int i=n-1;i>=1;--i){
        for(int c=1;c<=C;++c){
            if(w[i]<=c){
                m[i][c]=MAX(m[i+1][c],m[i+1][c-w[i]]+v[i]);

            }else{
                m[i][c]=m[i+1][c];
            }
        }
    }
    
    //输出最优解
    {
        int best=m[1][C];
        int i=1,c=10;
        while(i<n){
            if(m[i+1][c]!=best){
                c-=w[i];
                best-=v[i];
                printf(" %d ,", i);
            }
            ++i;
        }
        if(best>0){
            printf(" %d\n", i);
        }
    }
    
    return m[1][C];
}


int main()
{
    int v[]={0,6,3,5,4,6};
    int w[]={0,2,2,6,5,4};
    int C=10;
    int n=5;
    printf("packet=%d\n",packet(w,v,n,C));
    return 0;
}