背包问题

01背包

算法分析

01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。(摘自百度百科)
f[i][j]其中i表示有i件物品,j表示当时背包的容量,f[i][j]表示背包容量为j时,共有i件物品可选,能够得到的最大价值。
这样看来,就能得到其状态转移方程。
f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}
算法设计如下

int main()
{
    cin >> n >> v;
    for (int i = 1; i <= n; i++)
        cin >> c[i];//价值
    for (int i = 1; i <= n; i++)
        cin >> w[i];//体积
    for (int i = 1; i <= n; i++)
        f[i][0] = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= v; j++)
            if (j >= w[i])//背包容量够大
                f[i][j] = max(f[i - 1][j - w[i]] + c[i], f[i - 1][j]);
            else//背包容量不足
                f[i][j] = f[i - 1][j];
    cout << f[n][v] << endl;
    return 0;
}

典型例题

P1048采药
P1060开心的金明

Add a Comment

邮箱地址不会被公开。