AT4526 Knapsack 2

_JF_ · 2022-01-26 09:25:56 · 题解

AT4526 Knapsack 2

前置知识：01背包

最经典的一道题：有一个 M 公斤的背包,N 件物品 它们的重量是 W_1, W_2...W_n 它们的价值分别为 C_1,C_2,C_3...C_n 每个物品只有一件,问可以装入的最大价值。

设 f[i][x] 表示前 i 件物品 背包容量为 x 的最优价值 可以得到动态规划转移方程：

那么这个方程的含义是什么呢？其实 01 背包的本质就是取和不取。所以我们来份两种情况讨论：

1.取第 i 件物品,那么,f[i-1] 表示前 i-1 件物品的最优价值 x-w[i] 表示取该件物品所花费的空间 v[i] 表示取这件物品可以得到的价值

2.不取该件物品,那么就是继承上一个的最优解就可以了

最后在这两种情况之中取最优值 就是当前的 f[i][x] 的值了。

01背包的优化：

由上文可知,01背包的转移方程是 f[i][x]=\max(f[i-1][x],f[i][x-w[i]]+v[i])

其中的 f[i][j] 是由上一行的 f[i-1][x-w[i]] 和 f[i-1][j] 推过来的,所以完全可以将 f[i][j] 用 f[i] 来表示，所以方程为：

这个方程的意思是：f[i] 为重量为j时的最优价值，i-w 表示减去物品所需的空间。在 \max 中的 f[i] 中表示不装。

练习题目 AT4525 P1164

所以对于这一题来说,数据太大了 ,W 取到了 10^9 所以我们应该反过来考虑：

设 f[i][j] 表示前 i 个物品 总价值为 j 的最小重量 根据01背包的思想 我们继续来分类讨论（这里的 v[i] 表示价值 w[i] 表示重量）：

1.拿第 i 件：那么其他的物品就必须凑出 j-v[i] 的价值，由于我要拿第 i 件，所以前 i-1 件物品 就要腾出 w[i] 的空间，就这一种情况而言，他就必须包含 w[i] 的空间，所以整理一下，就是 f[i-1][j-v[i]]+w[i]

2.不拿第 i 件 则前i件就要拿出 j 的价值，所以这一段方程为 f[i-1][j]

由于数据问题，应该考虑压维

整理可得：

所以到这里，这道题就大体完成了，下面来看完整代码：

#include<bits/stdc++.h>
using namespace std;
int f[114514],n,m,w[114],v[114];
int main()
{
    int n,m;
    cin>>n>>m;
    int maxx=n*1000;//最坏的情况 开大开小都不行  
    for(int i=1;i<=n;i++)
        cin>>w[i]>>v[i];
    memset(f,0x3f3f,sizeof(f));// 初始值最大  
    f[0]=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=maxx;j>=v[i];j--)
        {
            f[j]=min(f[j],f[j-v[i]]+w[i]);
        }
    }
    for(int i=maxx;i;i--)
    {
        if(f[i]<=m)//如果当前的价值是小于或者等于它的，那么他就是最优解了 
        {
            cout<<i<<endl;
            return 0;
        }
    }
    return 0;
}