01背包问题

题目

有 N N N 件物品和一个容量为 V V V 的背包。放入第 i i i 件物品耗费的费用是 C i C_i Ci，得到的价值是 W i W_i Wi。求解将哪些物品装入背包可使价值总和最大。

基本思路

题目特点：每种物品仅一件，可以选择放或不放。

子问题定义状态： F [ i , v ] F[i, v] F[i,v] 表示前 i i i 件物品正好放入一个容量为 v v v 的背包可以获得的最大价值。

状态转移方程： F [ i , v ] = m a x { F [ i − 1 , v ] , F [ i − 1 , v − C i ] + W i } F[i, v] = max{F[i-1, v],F[i-1, v-C_i]+W_i} F[i,v]=max{ F[i−1,v],F[i−1,v−Ci]+Wi}

模板：

typedef long long ll;
const ll Inf = 0x3f3f3f3f;

ll ZeroOnePack(ll F[], ll C, ll W, ll Cap, ll sumW)
{
          
   
    for(int v = Cap; v >= max(Cap - sumW, C); v--)
        F[v] = max(F[v], F[v - C] + W);
}

ll Solve(const ll C[], const ll W[], const int N, const int Cap)
{
          
   
    ll F[Cap+1];
    //非恰好装满初始化
    memset(F,0,sizeof(F)); 
    //恰好装满初始化
    // for(int i=0;i<=V;i++)
    //     F[i] = -Inf;
    // F[0] = 0;

    ll sumW = 0;//常数优化
    for(int i=1; i <= N; i++)
        sumW += W[i];
    for(int i=1; i <= N; i++)
    {
          
   
        ZeroOnePack(F, C[i], W[i], Cap, sumW);
        sumW -= W[i];
    }
    return F[Cap];
}