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

九⼤背包问题专题--完全背包问题（详解，最优解）2.完全背包问题和01背包问题的区别：01背包问题：1件物品只能选或者不选完全背包问题：1件物品可以重复选多次，只要不超过总体积题⽬：问题：有N件物品和⼀个容量是V的背包。第i件物品的体积是vi，价值是wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包的容量，且价值最⼤。输⼊格式第⼀⾏有两个整数，N,V⽤空格隔开，分别表⽰物品数量和背包容积。接下来有N⾏，每⾏两个整数vi，wi，⽤空格隔开，分别表⽰第i件物品的体积和价值。输出格式输出⼀个整数，表⽰最⼤价值数据范围0保证每个物品只⽤1次从前往后考虑for(int i=0;i=v[i];j--) f[j]=max(f[j]，f[j-v[i]]+w[i])原因：保证状态转移时，算f[j]时，算的是f[i][j](第i个物品的j)，保证转移时，⽤的是f[i-1][j]f[j]=max(f[j],f[i-1][j-v[i]]+w[i]);⽽不是 f[j]=max(f[j,]f[i][j-v[i]]+w[i])从⼤到⼩枚举,v[i]>0,[j-v[i]]⼀定没有被算过，则它⼀定是f[i-1]的状态。完全背包从⼩到⼤枚举->保证在背包容量允许的条件下，每个物品可重复多次使⽤现在枚举第i个物品，体积从⼤到⼩枚举 for(int j=m,j>=v[i];j--) for(int k=0;k*v[i]<=j;k++) //选的物品数 f[j]=max(f[j],f[j-k*v[i]]+k*w[i]) //⼀个物品重复选多次，直到装不下，⼀定不包含当前的第i个物品算f[j]时，⽤来转移的状态⼀定是f[i-1]的算f[j]时，所有⽐j⼩的f[j]都没有被算过，上⾯所有的f[j-k*v[i]都没算过，都不包含第i个物品枚举选k个，对不同的k，更新刚才的状态，体积就是j-k*v[i]]，价值就是k*w[i]从⼩到⼤枚举，在算f[j]时，⽤j-v[i]这个状态，j-v[i]这个状态是被算过的,因为从⼩到⼤枚举，所以算f[j]时，⽐j⼩的都已经算过了，j-v[i]也在⾥⾯，所以j-v[i]这个状态也被算过了f[j-v[i]]表⽰考虑前i个物品，包括第i个物品的情况下，体积是j-v[i]时，最⼤价值是多少，可能已包含若⼲的当前第i个的物品。综上，从⼩到⼤更新状态，f[j-v[i]]包含第i个物品，证明从⼩到⼤枚举能枚举到最优解.证明:数学归纳法（迭代，递推关系）1.假设前i-1个物品考虑完之后，所有的f[j]都是符合的，所有f[j]表⽰体积是j的情况下，它的最⼤价值就是f[j]初始化:f[0][0]正确2.考虑完第i个物品后，所有f[j]也是符合的对某⼀个j⽽⾔，把j确定，最优解⾥⾯包含k个v[i]，第i个物品从⼩到⼤枚举，⼀定可以枚举到f[j-k*v[i]]状态，算此状态时，⽤f[j-k*v[i]-v[i]]+w[i]更新状态（此最优解不包含v[i]）,反之f[j-k*v[i]]不包含，所以不会更新，取完max后⼀定是原来的数f[j-k*v[i]]此状态已算完接着算(k-1)*v[i]状态:f[j-(k-1)*v[i]]会⽤f[j-v[i]]+w[i])更新它，更新之后变为:f[j-k*v[i]-v[i]]+w[i]综上：f[j-(k-1)*v[i]]这个状态会⽤f[j-k*v[i]]（⼀个v[i]都不包含）这个状态更新；枚举完⼀个之后就会包含⼀个v[i],依次类推：算f[j]时，⽤f[j-v[i]]+w[i])（此状态⼀定计算过只包含k-1个物品这个状态）更新，所以说f[j]这个物品枚举了包含k个v[i]如果最后结果中包含k个v[i]，那么f[j]就⼀定枚举到过这种状态所以f[j]就⼀定会枚举到最优解举例：1、前1个物品中：f[1]=2,f[2]=4,f[3]=6,f[4]=8,f[5]=10，显然f[j]都是正确的。2、假设在前i-1个物品中，f[j]都是正确的。3、在前i个物品中，对于某个j⽽⾔，如果最优解包含k个v[i]，则⼀定会枚举到f[j-kv[i]]，f[j-kv[i]]是如何得到的呢?f[j-kv[i]=max{f[j-kv[i]],f[j-kv[i]-v[i]]+w[i]} （由于j正序，f[j-kv[i]]为前i-1个物品的值，f[j-k*v[i]-v[i]]为前i个物品的值).最后会传递到max{f[v[i]],f[0]+w[i]}处。因为f[v[i]]⼀定正确（2中已假设前i-1个物品中的f[j]全都正确），f[0]⼀定正确=0，w[i]⼀定正确，所max{f[v[i]],f[0]+w[i]}⼀定正确=>f[j-k*v[i]]⼀定正确=>f[j]⼀定正确.时间复杂度:1000000代码：#include#include#includeusing namespace std;const int N=1010;int n,m;

int f[N];int main(){ cin>>n>>m; for(int i=0;i

int v,w; cin>>v>>w; for(int j=v;j<=m;j++) //⼩到⼤枚举体积，＜v的不枚举

f[j]=max(f[j],f[j-v]+w); }

/*初始化的时候把所有的 f[i]都初始化为0

/f[m]

表⽰体积

⼩于等于m的情况下

，所有⽅法⾥⾯

/转移的时候不⼀定是从f[0]转移过来的，可以从任意⼀个状态转移

/当⽤不完整个背包的容量的时候

，假设剩k容量就可以从k转移

/则⼀定可以枚举到

最优解⼀样的选法

，因为体积变成了⼀样的

/假设最优解⽤了m-k的体积，f[m]就⼀定可以从k开始枚举

，也只⽤了 m-k的体积

也会枚举到最优解

，所以f[m]表⽰的就是体积⼩于等于 m的情况下的最优解 */

cout<

return 0;}若题⽬问体积恰好为m的情况下，最⼤价值为多少?除f[0]=0在初始化时所有f[i]初始化为负⽆穷

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

九⼤背包问题专题--完全背包问题（详解，最优解）2.完全背包问题和01背包问题的区别：01背包问题：1件物品只能选或者不选完全背包问题：1件物品可以重复选多次，只要不超过总体积题⽬：问题：有N件物品和⼀个容量是V的背包。第i件物品的体积是vi，价值是wi。求解将哪些物品装⼊背包，可使这些物品的总体积不超过背包的容量，且价值最⼤。输⼊格式第⼀⾏有两个整数，N,V⽤空格隔开，分别表⽰物品数量和背包容积。接下来有N⾏，每⾏两个整数vi，wi，⽤空格隔开，分别表⽰第i件物品的体积和价值。输出格式输出⼀个整数，表⽰最⼤价值数据范围0保证每个物品只⽤1次从前往后考虑for(int i=0;i=v[i];j--) f[j]=max(f[j]，f[j-v[i]]+w[i])原因：保证状态转移时，算f[j]时，算的是f[i][j](第i个物品的j)，保证转移时，⽤的是f[i-1][j]f[j]=max(f[j],f[i-1][j-v[i]]+w[i]);⽽不是 f[j]=max(f[j,]f[i][j-v[i]]+w[i])从⼤到⼩枚举,v[i]>0,[j-v[i]]⼀定没有被算过，则它⼀定是f[i-1]的状态。完全背包从⼩到⼤枚举->保证在背包容量允许的条件下，每个物品可重复多次使⽤现在枚举第i个物品，体积从⼤到⼩枚举 for(int j=m,j>=v[i];j--) for(int k=0;k*v[i]<=j;k++) //选的物品数 f[j]=max(f[j],f[j-k*v[i]]+k*w[i]) //⼀个物品重复选多次，直到装不下，⼀定不包含当前的第i个物品算f[j]时，⽤来转移的状态⼀定是f[i-1]的算f[j]时，所有⽐j⼩的f[j]都没有被算过，上⾯所有的f[j-k*v[i]都没算过，都不包含第i个物品枚举选k个，对不同的k，更新刚才的状态，体积就是j-k*v[i]]，价值就是k*w[i]从⼩到⼤枚举，在算f[j]时，⽤j-v[i]这个状态，j-v[i]这个状态是被算过的,因为从⼩到⼤枚举，所以算f[j]时，⽐j⼩的都已经算过了，j-v[i]也在⾥⾯，所以j-v[i]这个状态也被算过了f[j-v[i]]表⽰考虑前i个物品，包括第i个物品的情况下，体积是j-v[i]时，最⼤价值是多少，可能已包含若⼲的当前第i个的物品。综上，从⼩到⼤更新状态，f[j-v[i]]包含第i个物品，证明从⼩到⼤枚举能枚举到最优解.证明:数学归纳法（迭代，递推关系）1.假设前i-1个物品考虑完之后，所有的f[j]都是符合的，所有f[j]表⽰体积是j的情况下，它的最⼤价值就是f[j]初始化:f[0][0]正确2.考虑完第i个物品后，所有f[j]也是符合的对某⼀个j⽽⾔，把j确定，最优解⾥⾯包含k个v[i]，第i个物品从⼩到⼤枚举，⼀定可以枚举到f[j-k*v[i]]状态，算此状态时，⽤f[j-k*v[i]-v[i]]+w[i]更新状态（此最优解不包含v[i]）,反之f[j-k*v[i]]不包含，所以不会更新，取完max后⼀定是原来的数f[j-k*v[i]]此状态已算完接着算(k-1)*v[i]状态:f[j-(k-1)*v[i]]会⽤f[j-v[i]]+w[i])更新它，更新之后变为:f[j-k*v[i]-v[i]]+w[i]综上：f[j-(k-1)*v[i]]这个状态会⽤f[j-k*v[i]]（⼀个v[i]都不包含）这个状态更新；枚举完⼀个之后就会包含⼀个v[i],依次类推：算f[j]时，⽤f[j-v[i]]+w[i])（此状态⼀定计算过只包含k-1个物品这个状态）更新，所以说f[j]这个物品枚举了包含k个v[i]如果最后结果中包含k个v[i]，那么f[j]就⼀定枚举到过这种状态所以f[j]就⼀定会枚举到最优解举例：1、前1个物品中：f[1]=2,f[2]=4,f[3]=6,f[4]=8,f[5]=10，显然f[j]都是正确的。2、假设在前i-1个物品中，f[j]都是正确的。3、在前i个物品中，对于某个j⽽⾔，如果最优解包含k个v[i]，则⼀定会枚举到f[j-kv[i]]，f[j-kv[i]]是如何得到的呢?f[j-kv[i]=max{f[j-kv[i]],f[j-kv[i]-v[i]]+w[i]} （由于j正序，f[j-kv[i]]为前i-1个物品的值，f[j-k*v[i]-v[i]]为前i个物品的值).最后会传递到max{f[v[i]],f[0]+w[i]}处。因为f[v[i]]⼀定正确（2中已假设前i-1个物品中的f[j]全都正确），f[0]⼀定正确=0，w[i]⼀定正确，所max{f[v[i]],f[0]+w[i]}⼀定正确=>f[j-k*v[i]]⼀定正确=>f[j]⼀定正确.时间复杂度:1000000代码：#include#include#includeusing namespace std;const int N=1010;int n,m;

int f[N];int main(){ cin>>n>>m; for(int i=0;i

int v,w; cin>>v>>w; for(int j=v;j<=m;j++) //⼩到⼤枚举体积，＜v的不枚举

f[j]=max(f[j],f[j-v]+w); }

/*初始化的时候把所有的 f[i]都初始化为0

/f[m]

表⽰体积

⼩于等于m的情况下

，所有⽅法⾥⾯

/转移的时候不⼀定是从f[0]转移过来的，可以从任意⼀个状态转移

/当⽤不完整个背包的容量的时候

，假设剩k容量就可以从k转移

/则⼀定可以枚举到

最优解⼀样的选法

，因为体积变成了⼀样的

/假设最优解⽤了m-k的体积，f[m]就⼀定可以从k开始枚举

，也只⽤了 m-k的体积

也会枚举到最优解

，所以f[m]表⽰的就是体积⼩于等于 m的情况下的最优解 */

cout<

return 0;}若题⽬问体积恰好为m的情况下，最⼤价值为多少?除f[0]=0在初始化时所有f[i]初始化为负⽆穷