AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 校园
  • 应用
  • 文章
    • 题解
    • 分享
    • 问答
  • 吐槽
  • 登录/注册

AcWing 2. 01背包问题(状态转移方程讲解)    原题链接    简单

作者: 作者的头像   深蓝 ,  2019-04-05 22:15:11 ,  所有人可见 ,  阅读 68389


733


456

21.2.10更新:

  • 代码变量命名与题目一致
  • 题解思路变得更详细了
  • 加入了不断优化版本的解法

1. 题目介绍

有 $N$ 件物品和一个容量为 $V$ 的背包,每件物品有各自的价值且只能被选择一次,要求在有限的背包容量下,装入的物品总价值最大。

「0-1 背包」是较为简单的动态规划问题,也是其余背包问题的基础。

动态规划是不断决策求最优解的过程,「0-1 背包」即是不断对第 $i$ 个物品的做出决策,「0-1」正好代表不选与选两种决定。

2. 题解代码(C++)

2.1 版本1 二维

(1)状态f[i][j]定义:前 $i$ 个物品,背包容量 $j$ 下的最优解(最大价值):

  • 当前的状态依赖于之前的状态,可以理解为从初始状态f[0][0] = 0开始决策,有 $N$ 件物品,则需要 $N$ 次决 策,每一次对第 $i$ 件物品的决策,状态f[i][j]不断由之前的状态更新而来。

(2)当前背包容量不够(j < v[i]),没得选,因此前 $i$ 个物品最优解即为前 $i-1$ 个物品最优解:

  • 对应代码:f[i][j] = f[i - 1][j]。

(3)当前背包容量够,可以选,因此需要决策选与不选第 $i$ 个物品:

  • 选:f[i][j] = f[i - 1][j - v[i]] + w[i]。
  • 不选:f[i][j] = f[i - 1][j] 。
  • 我们的决策是如何取到最大价值,因此以上两种情况取 max() 。

代码如下:

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int v[MAXN];    // 体积
int w[MAXN];    // 价值 
int f[MAXN][MAXN];  // f[i][j], j体积下前i个物品的最大价值 

int main() 
{
    int n, m;   
    cin >> n >> m;
    for(int i = 1; i <= n; i++) 
        cin >> v[i] >> w[i];

    for(int i = 1; i <= n; i++) 
        for(int j = 1; j <= m; j++)
        {
            //  当前背包容量装不进第i个物品,则价值等于前i-1个物品
            if(j < v[i]) 
                f[i][j] = f[i - 1][j];
            // 能装,需进行决策是否选择第i个物品
            else    
                f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);
        }           

    cout << f[n][m] << endl;

    return 0;
}

2.2 版本2 一维

将状态f[i][j]优化到一维f[j],实际上只需要做一个等价变形。

为什么可以这样变形呢?我们定义的状态f[i][j]可以求得任意合法的i与j最优解,但题目只需要求得最终状态f[n][m],因此我们只需要一维的空间来更新状态。

(1)状态f[j]定义:$N$ 件物品,背包容量j下的最优解。

(2)注意枚举背包容量j必须从m开始。

(3)为什么一维情况下枚举背包容量需要逆序?在二维情况下,状态f[i][j]是由上一轮i - 1的状态得来的,f[i][j]与f[i - 1][j]是独立的。而优化到一维后,如果我们还是正序,则有f[较小体积]更新到f[较大体积],则有可能本应该用第i-1轮的状态却用的是第i轮的状态。

(4)例如,一维状态第i轮对体积为 $3$ 的物品进行决策,则f[7]由f[4]更新而来,这里的f[4]正确应该是f[i - 1][4],但从小到大枚举j这里的f[4]在第i轮计算却变成了f[i][4]。当逆序枚举背包容量j时,我们求f[7]同样由f[4]更新,但由于是逆序,这里的f[4]还没有在第i轮计算,所以此时实际计算的f[4]仍然是f[i - 1][4]。

(5)简单来说,一维情况正序更新状态f[j]需要用到前面计算的状态已经被「污染」,逆序则不会有这样的问题。

状态转移方程为:f[j] = max(f[j], f[j - v[i]] + w[i] 。

for(int i = 1; i <= n; i++) 
    for(int j = m; j >= 0; j--)
    {
        if(j < v[i]) 
            f[i][j] = f[i - 1][j];  // 优化前
            f[j] = f[j];            // 优化后,该行自动成立,可省略。
        else    
            f[i][j] = max(f[i - 1][j], f[i - 1][j - v[i]] + w[i]);  // 优化前
            f[j] = max(f[j], f[j - v[i]] + w[i]);                   // 优化后
    }    

实际上,只有当枚举的背包容量 >= v[i] 时才会更新状态,因此我们可以修改循环终止条件进一步优化。

for(int i = 1; i <= n; i++)
{
    for(int j = m; j >= v[i]; j--)  
        f[j] = max(f[j], f[j - v[i]] + w[i]);
} 

关于状态f[j]的补充说明

二维下的状态定义f[i][j]是前 $i$ 件物品,背包容量 $j$ 下的最大价值。一维下,少了前 $i$ 件物品这个维度,我们的代码中决策到第 $i$ 件物品(循环到第i轮),f[j]就是前i轮已经决策的物品且背包容量 $j$ 下的最大价值。

因此当执行完循环结构后,由于已经决策了所有物品,f[j]就是所有物品背包容量 $j$ 下的最大价值。即一维f[j]等价于二维f[n][j]。

2.3 版本3 优化输入

我们注意到在处理数据时,我们是一个物品一个物品,一个一个体积的枚举。

因此我们可以不必开两个数组记录体积和价值,而是边输入边处理。

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 1005;
int f[MAXN];  // 

int main() 
{
    int n, m;   
    cin >> n >> m;

    for(int i = 1; i <= n; i++) {
        int v, w;
        cin >> v >> w;      // 边输入边处理
        for(int j = m; j >= v; j--)
            f[j] = max(f[j], f[j - v] + w);
    }

    cout << f[m] << endl;

    return 0;
}

215 评论


用户头像
wengyan17   6天前     回复

orz 这是我看见过对二维到一维优化讲的最清楚的一个了


用户头像
魔法学徒   11天前     回复

版本三好棒,借鉴走了😚


用户头像
baoᴗo   14天前     回复

牛逼


用户头像
陆修远   17天前     回复

非常厉害$orz$,如果能配上一个贴图就更好了,其实也是很好写的~


用户头像
良_48   1个月前     回复

若j从小到大,f[j-v[i]]中,由于j-v[i]小于j,f[j-v[i]]已经在i这层循环被计算了,而我们想要的f[j-v[i]]应该是i-1层循环里面的,所以j从大到小的话保证此时的f[j-v[i]]还未被计算,也就是第i-1层的数据


用户头像
灯未灭人未眠   1个月前     回复

厉害啊


用户头像
可爱抱抱呀   1个月前     回复

Java 版:

//通过了 12/12个数据  运行时间: 331 ms  运行空间: 28980 KB  2022年5月9日 12:17
import java.util.*;
import java.io.*;
import java.math.*;
public class Main{
    public static void main(String args[]) throws IOException{
        Read sc=new Read();
        int n=sc.nextInt(),V=sc.nextInt();
        int v[]=new int[n],w[]=new int[n];
        for(int i=0;i<n;i++){
            v[i]=sc.nextInt();//体积
            w[i]=sc.nextInt();//价值
        }
        int ans[][]=new int[n+1][V+1];//ij表示的是在前i个货物中取得体积不超过j的时候的最大价值
        for(int i=1;i<=n;i++){
            for(int j=1;j<=V;j++){
                ans[i][j]=ans[i-1][j];
                if(j>=v[i-1]){
                    ans[i][j]=Math.max(ans[i][j],ans[i-1][j-v[i-1]]+w[i-1]);
                }
            }
        }
        System.out.print(ans[n][V]);
    }
}
class Read{
    private BufferedReader bf;
    private StringTokenizer st;
    public Read(){
        bf=new BufferedReader(new InputStreamReader(System.in));
        st=new StringTokenizer("");
    }
    public String nextLine() throws IOException{
        return bf.readLine();
    }
    public String next() throws IOException{
        while(!st.hasMoreTokens()){
            st=new StringTokenizer(bf.readLine());
        }
        return st.nextToken();
    }
    public int nextInt() throws IOException{
        return Integer.parseInt(next());
    }
    public long nextLong() throws IOException{
        return Long.parseLong(next());
    }
    public double nextDouble() throws IOException{
        return Double.parseDouble(next());
    }
    public BigInteger nextBigInteger() throws IOException{
        return new BigInteger(next());
    }
}
用户头像
徐盛哥哥的刀   1个月前     回复

没想到又在这里活捉了抱抱(滑稽)

用户头像
可爱抱抱呀   1个月前    回复了 徐盛哥哥的刀 的评论     回复

😁😁


用户头像
iwjns   1个月前     回复

牛逼


用户头像
梦忆晴天   1个月前     回复

tql


用户头像
帷幕月影   1个月前     回复

yyds


用户头像
小太阳_15   2个月前     回复

nb!


用户头像
布丁君   2个月前     回复

nb


用户头像
linminqingying   2个月前     回复

nice


用户头像
RIP   2个月前     回复

兄弟你写的太棒了!!!!!!!!!!

用户头像
RIP   2个月前     回复

这个题解写的真的太有水平了!!!!

用户头像
Littlecat   2个月前    回复了 RIP 的评论     回复

你的字为什么比我大

用户头像
RIP   2个月前    回复了 Littlecat 的评论     回复

可以用markdown语法,我用的是H1标头

用户头像
努力的草鱼   1个月前    回复了 RIP 的评论     回复

[HTML_REMOVED]


用户头像
fangeha   2个月前     回复

这个不是按照状态决策来理解的么? 我感觉 y总 的集合理解法更清晰易懂。
f[i][j] 表示 一个 集合的属性,然后状态转移 就是对 集合的拆分。


用户头像
洛云   2个月前     回复

抢到了第660个赞和第400个收藏QwQ


用户头像
OIer02   2个月前     回复

for循环变量为什么不能从0开始取?从零开始取,结果不对

用户头像
我可以认真点吗   2个月前     回复

这里的i是有实际含义的 i=0的实际含义是0个物品,显然不对

用户头像
riz9   2个月前     回复

f[0-1]显然越界了

用户头像
嗯哼_16   2个月前     回复

从0开始 i<n 不是<=


用户头像
无心_6   2个月前     回复

为啥压到一维后状态f[j]的定义是:N 件物品,背包容量j下的最优解。
可不可以是 M容量下,j件物品下的最优解


用户头像
haibinyuxinmei   2个月前     回复

真不错


用户头像
为止   2个月前     回复

for(int j = 1; j <= m; j++)是什么意思呢,一直不明白,j<背包容量??

用户头像
Little_Bee_Bill_Duck   2个月前     回复

我理解是背包不一定要刚好装满时的价值最大,所以让背包的容量从0-m遍历找到最大价值时的j就行了


你确定删除吗?

© 2018-2022 AcWing 版权所有  |  京ICP备17053197号-1
用户协议  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息