如果使用顺序，会先更新f[4],再更新f[7]，对于这个书包问题来讲，就是有可能，在更新f[4]的时候，已经把这次能加的物品加进来了，然后更新f[7]的时候，还有可能再加一次，所以必须使用逆序，保证，f[4]是没有加入新物品前，背包里的最优解。

你解释的好啊！！

miao

# tql

看你的解释懂了

还不懂背包问题的朋友们可以看看这篇博客，感觉很详细：https://blog.csdn.net/raelum/article/details/128996521

明白了，感谢！

万分感谢，看了你这篇才懂了那个优化成一维的，以前一直看不懂，么么哒

从后往前遍历是为了避免用到f[j - v[i]]的时候，f[j - v[i]]已经被选择本类物品时更新了(也就是我们要的是上一种物品容量 j-v[i]时最优状态下的f[j-v[i]], 而不是本类物品计算时的覆盖在之前数据上的 ‘痕迹 ’ ，这个时候的f[j-v[i]]就不是继承以往数据的最优值了，这样的话是利用不到上面循环已经计算过的值的，也算不出最优值)顺序计算的话，第四列的12是直接在第二列的6上加的，肯定不对。 如果使用逆序的话，先计算的数据不会覆盖后计算的数据，计算第一层的时候数组都是0，很 ‘干净’。需要替换数据时是先调用之前的结果对比择优再覆盖就没有问题了(蒟蒻发言o.o)
样例
4种物品 容量为5
2 6
3 5
5 5
1 3
数组下标(容量) 数组下标(容量)
顺序 1->5 逆序 5->1
0 6 6 12 12 6 6 6 6 0
0 0 6 12 12 11 6 6 6 0
0 0 0 0 12 11 6 6 6 0
3 6 9 12 15 11 9 9 6 3

#### Or2

说白了就是上一次记录的值被覆盖掉了

如果是顺序，f[4]会在f[7]之前更新，这时本该用到上一次的f[i - 1][4]就会变成f[i][4],因此顺序会污染数据。而当逆序时，是先更新f[7]再更新f[4]，这时的f[4]还没有更新，就还是上一轮的f[i - 1][4]

把细节解释出来了，tql

nb！惊为天人！

y总没有总结背包问题模板，需要模板的可以去看看这个博客： https://blog.csdn.net/m0_61654975/article/details/141210427

完全背包使用顺序用你这个解释也很好理解。

若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层的数据

妙

这个比较清晰

清晰

一语惊醒梦中人

棒棒的！！！

or2

orz

##一维数组倒序详细过程模拟：
首先我们要注意到f数组在每一层都会被赋值（也就是说f数组中的一些元素是会被重复使用的）

### 一维数组背包正序代码打印中间状态：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int n, m;
int f[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    for (int i = 1; i <= n; i ++ ) {
        printf("第%d层数据：\n", i);
        for (int j = v[i]; j <= m; j ++ ) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            printf("f[%d] = max(f[%d], f[%d] + w[%d])\n", j, j, j - v[i], i);
        }
    }

    cout << f[m] << endl;
    return 0;
}

### 一维数组背包逆序代码打印中间状态：

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N];
int n, m;
int f[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

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

    for (int i = 1; i <= n; i ++ ) {
        printf("第%d层数据：\n", i);
        for (int j = m; j >= v[i]; j -- ) {
            f[j] = max(f[j], f[j - v[i]] + w[i]);
            printf("f[%d] = max(f[%d], f[%d] + w[%d])\n", j, j, j - v[i], i);
        }
    }

    cout << f[m] << endl;
    return 0;
}

补充：用一个额外数组g保存第i-1层的状态就可以从小到大枚举体积了

#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int v[N], w[N], g[N], f[N];
int n, m;

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

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

    cout << f[m] << endl;
    return 0;
}

非常感谢，终于看懂了

谢谢佬~

ORZ!!!

感谢

你解释的好啊！！！

一眼丁真

你是假的 我是真的！

雪豹闭嘴

同意，礼堂顶针_才是正版，因为他喜欢瑞克5代

好好好！

放雪豹出来吼两声，直接证明你是正版

雪豹被阿妈拉走了

不过为什么他的赞比Y总多（问号）

我感觉更通用的解释就是保证得到新状态的时候，所根据的仍是老状态的数据得到新状态。如果从前往后，则有可能使得当前所更新状态的老状态数据已经被覆盖掉。举个例子，我要更新第i行的p[7]数据，所根据的是第i - 1行的p[4]老数据，若从前往后遍历，则在更新i行的p[7]之前，p[4]已经被更新为第i行的数据了。

诶要老哥，这一圈下来就看懂你这个了，强强强！

1.要明白为什么从大到小更新就要先明白f[j]的更新是基于i-1轮的
2.从小到大排序的情况下，j - v[i] 的小体积情况是刚刚更新的i轮的，那么假如f[ j - v [i] ]恰好加了第i件物品价值最大的情况下，此时 f[ j - v[i] ] + w[i] 的值又是较大的，那么又加了一遍第i件物品，则不符合01背包仅能增加一次的规定，那么从大到小会不会有这种情况呢，不会，因为大的先更新，用到的小的还是第 i - 1 轮的，而 小空间背包的更新需要更小空间的背包的第i -1轮的值，则不会影响

赞！

赞

就你的看懂了orz

牛的

有没有大佬解答一下，在二维dp中，每次的物品体积V[i]都与背包的整个区间进行对比(为什么不是去掉上个物品的体积)？哪个地方体现了容量的限制？

同问

对于二维dp，v[i]都与j~(0-m)体积进行比较，直到j>=v[i]。如果j==v[i],（背包只能放得下当前物品）那么f[i][j]=f[i-1][0]+w[i];显然，f[i-1][0]=0(既可以直接看，也可以根据 f[i] [j]= f[i-1] [j] 推)然后，比较同背包容积下，取i-1个物品和取当前物品哪个价值高，若当前物品价值高，就更新为当前物品的价值。相当把原来不值钱的扔了，放当前价值更高的。否则，f[i][j]仍然存f[i-1][j]物品的价值
j>v[i]同理,f[i][j]=f[i][j-v[i]]+w[i];f[i][j]由f[i-1][j-v[i]]更新而来。这一步体现了容积的限制。未放i物品时，背包内最大价值存放方式为f[i-1][j-v[i]],放i物品后，变成f[i][j]; 建议用数据模拟一下，比较容易理解

谢谢大佬，我的看法(初学者，有误请大家指出)：细分为三种情况：
①当前物品的体积v[i]大于背包总容量j时，那么就取只放前i-1个物品，总体积小于j的方案就行；
②当前物品的体积v[i]等于背包总容量j时，那么此时j - v[i] = 0，即f[ i - 1，j - v[i] ] + w[i] = f[i-1, 0] + w[i] = 0 + w[i] = w[i]，所以f[i,j] = max(f[i-1,j] , w[i])，此时二者选最大值的方案即可，【也就是大佬第一段话的意思】
③当前物品的体积v[i]小于背包总容量j时，此时j - v[i] > 0 ，也就是说背包用来放当前物品i后还有剩余的体积j - v[i] ，那么先放入当前物品i，再选择前i-1个物品且总体积小于等于j - v[i]的方案，所得的价值就是f[i - 1,j - v[i]] + w[i]，再把此价值与f[i - 1,j]取max即可

很详细啊，厉害的

tql

这个真的看得懂，好感动呜呜呜

orz

orz

$orz$

有大佬知道 在01背包中在决定是否放第i个物品时，为什么是拿物品i的体积和背包最大容量比较，而不是和背包剩余容量比较？哪个地方体现了容量的限制？

楼上发表了我的看法，有误请同学指出

太详细了，懂了

牛！ 你的题解让我找到了点赞按钮

我想问变成一维数组后为什么是 j >= v[i]，而不是j>=1作为循环结束的条件

如果j>=1作为循环结束的条件，循环内还要判断j>=v[i]，这里相当于是合并成一步了

但是在j>=1 的循环条件下要进行判断 当j<v[i]时候，f[i][j]=f[i-1][j],如果j从v[i]开始,那么这一步就没有了，没有了为什么结果还是对的呢？

当j＜v(i）时，就说明当前j也就是背包容量放不下当前物品了，此时一维数组fj就没有更新的必要了啊，直接fj等于fj，直到你说的条件结束，其实可以写，但没必要

这一重循环是干嘛的
for(int j = 1; j <= m; j++)

为什么数组没有赋初始值也可以成功。。。小白提问，感觉f[0][1]的值怎么确定呢？

C++ 数组没初始值，默认为0

定义全局变量未赋值默认为0

感谢感谢

orz

orz是啥意思（我是土狗😶😶）

以orz拟人体跪拜的姿势，表达了作者对大佬的膜拜之情，从侧面突出了大佬的层级之高以及对大佬的题解对作者的影响之大，言简意赅，却又富有冲击力，生动形象的表现了作者对题解大佬的崇拜之意。

原来学计算机也可以有那么好的文学素养

哈哈了解了了解了多谢多谢

## orz
### 及其延伸式：
- Orz
- or2
- Or2

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());
    }
}

没想到又在这里活捉了抱抱（滑稽）

😁😁

在这里也能碰到抱抱！

抱抱姐（捉

为什么会理解得这么简单啊？它说每个物品只能选一次，要容量不超过的条件下价值最大。不一定要按照输入顺序顺次选取吧？不是应该判断选哪几样在容量不超过时总价值最大吗？

有点不清楚为什么j也是要从0开始算

逆序是因为，一维数组没有二维数组第i层的限制条件，所以f4不是第i-1层的数据，而是第i层的新更新的数据，因为顺序是f4先更新，再使用到f7中

for i
    for j in 正序
         此时 j-v[i] 是这一层（也就是i）对应的j-v[i]（由于从小到大，在这一层 i 的时候先更新了j-v[i]

而如果
for i
    for j in 逆序
        此时 j-v[i] 是上一层（也就是i - 1）对应的j-v[i]（由于从大到小，这时候的j-v[i]仍然保留着上一层（i - 1）的状态