2023年8月1日发(作者：)

01，完全背包问题的⼀维数组（博主懒，就不写⼆位数组了，⼤家也可以百度到的）

先来说明背包问题：

有⼀堆已知重量（weight[]）以及价值（value[]）的物品，在每件物品只能拿⼀次的情况下，在a件物品中选取重量不超过j的最⼤价值

设置f[v]为能拿到v件的物品时对应的最⼤价值，即求f[a]；

直接上核⼼代码（也就是状态⽅程）： for (int i = 1;i < a;i++)

{ for (int v=j;v>0;v--)

{ if (v >= weight[i]) { f[v] =

f[v] > (f[v- weight[i]] + value[i])? f[v]: f[v- weight[i]] + value[i]; } } }（敲⿊板）

注意，第⼆个for (int v=j;v>0;v–) 是从v=j倒序开始更新f[j]；

也就是说，当f[v]开始更新的时候，

f[v] = f[v] > (f[v- weight[i]] + value[i])? f[v]: f[v- weight[i]] + value[i];

此时的f[v]其实是跟上⼀个i-1的时候的f[v]去⽐较（上⼀个的f[v]是不能取到第i件物品的）。更新之后如果能取到第i个物品，那么就⽐较不取第i件物品跟取到第i件物品的价值。取⼤（f[v]全部初始化为0）

so，注意理解。f[v]是能取第i件以及之前所有物品的最⼤价值，每次的⽐较都是围绕能取第i件（含之前的物品）以及第i-1件（含之前的物品）的价值。

上⾯是01背包问题。下⾯是完全背包for (int i = 1;i < a;i++)

{ for (int v=1;v

{ if (v >= weight[i]) { f[v] =

f[v] > (f[v- weight[i]] + value[i])? f[v]: f[v- weight[i]] + value[i]; } } }注意，修改的仅仅是第⼆个for循环的顺序。由倒序改成顺序。

01背包中，为什么要倒序，因为每个背包只能拿⼀次。那么在每⼀次的i，v循环中，我们仅仅需要知道的是第i件物品能不能放下，能的话跟上⼀次的⽐较就可以。因为上⼀次循环的f[v]是在i-1件物品只能拿⼀次的情况下的最⼤值，倒序是为了仅跟上次的状态（i-1件物品）⽐较。完全背包中相反，采⽤顺序。

举例，第i件物品重量是1，价值是value；

那么这个时候要先更新f[1]，⽐较前i-1件物品的f[1]以及value；

然后到f[2]，f[2]就应该max（前i件物品的f[2-1]+value，前i-1件物品的f[2-1]）然后跟前i-1件物品的f[2]⽐较。

f[3]同理。⼀路推到f[v]。

完全背包⽐较的应该是：前i件物品的f[v-weight]+value，前i-1件物品的f[v-weight]，前i-1件物品的f[v]这三者的⽐较。也就是当前状态，需要先推导出重量v之前的当前状态，才能得到最⼤值。这就是完全背包

2023年8月1日发(作者：)

01，完全背包问题的⼀维数组（博主懒，就不写⼆位数组了，⼤家也可以百度到的）

先来说明背包问题：

有⼀堆已知重量（weight[]）以及价值（value[]）的物品，在每件物品只能拿⼀次的情况下，在a件物品中选取重量不超过j的最⼤价值

设置f[v]为能拿到v件的物品时对应的最⼤价值，即求f[a]；

直接上核⼼代码（也就是状态⽅程）： for (int i = 1;i < a;i++)

{ for (int v=j;v>0;v--)

{ if (v >= weight[i]) { f[v] =

f[v] > (f[v- weight[i]] + value[i])? f[v]: f[v- weight[i]] + value[i]; } } }（敲⿊板）

注意，第⼆个for (int v=j;v>0;v–) 是从v=j倒序开始更新f[j]；

也就是说，当f[v]开始更新的时候，

f[v] = f[v] > (f[v- weight[i]] + value[i])? f[v]: f[v- weight[i]] + value[i];

此时的f[v]其实是跟上⼀个i-1的时候的f[v]去⽐较（上⼀个的f[v]是不能取到第i件物品的）。更新之后如果能取到第i个物品，那么就⽐较不取第i件物品跟取到第i件物品的价值。取⼤（f[v]全部初始化为0）

so，注意理解。f[v]是能取第i件以及之前所有物品的最⼤价值，每次的⽐较都是围绕能取第i件（含之前的物品）以及第i-1件（含之前的物品）的价值。

上⾯是01背包问题。下⾯是完全背包for (int i = 1;i < a;i++)

{ for (int v=1;v

{ if (v >= weight[i]) { f[v] =

f[v] > (f[v- weight[i]] + value[i])? f[v]: f[v- weight[i]] + value[i]; } } }注意，修改的仅仅是第⼆个for循环的顺序。由倒序改成顺序。

01背包中，为什么要倒序，因为每个背包只能拿⼀次。那么在每⼀次的i，v循环中，我们仅仅需要知道的是第i件物品能不能放下，能的话跟上⼀次的⽐较就可以。因为上⼀次循环的f[v]是在i-1件物品只能拿⼀次的情况下的最⼤值，倒序是为了仅跟上次的状态（i-1件物品）⽐较。完全背包中相反，采⽤顺序。

举例，第i件物品重量是1，价值是value；

那么这个时候要先更新f[1]，⽐较前i-1件物品的f[1]以及value；

然后到f[2]，f[2]就应该max（前i件物品的f[2-1]+value，前i-1件物品的f[2-1]）然后跟前i-1件物品的f[2]⽐较。

f[3]同理。⼀路推到f[v]。

完全背包⽐较的应该是：前i件物品的f[v-weight]+value，前i-1件物品的f[v-weight]，前i-1件物品的f[v]这三者的⽐较。也就是当前状态，需要先推导出重量v之前的当前状态，才能得到最⼤值。这就是完全背包