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

01背包问题，完全背包问题的⼆维数组，⼀维数组的解答关于01背包问题，完全背包问题，这⾥就不过多阐述。这⾥只是总结⼀下这两个问题的⼆维数组，⼀维数组的两种表达⽅式。为什么要⽤⼀位数组，两个原因：1.节约空间（⼆维变⼀维）2.时间复杂度降为线性。直接上代码，如果对01背包问题，完全背包问题有问题的推荐看⼀下《背包九讲》和其他博客。1. 背包九讲：2. 01背包问题可视化的⽹站：（这个是真的好⽤，你只要输⼊条件就给你画出所有的情况）3. 挺详细的⼀个博客：切⼊正题，进⾏代码总结：01背包问题：⼆维数组：void FindMax()//动态规划 { int i,j; //填表 for(i=1;i<=number;i++) { for(j=1;j<=capacity;j++) { if(jV[i-1][j-w[i]]+v[i])//不装价值⼤ { V[i][j]=V[i-1][j]; } else//前i-1个物品的最优解与第i个物品的价值之和更⼤ { V[i][j]=V[i-1][j-w[i]]+v[i]; } } } } }⼀维数组： void FindMaxBetter()//优化空间后的动态规划 { int i,j; for(i=1;i<=number;i++) { for(j=capacity;j>=w[i];j--) { if(B[j]<=B[j-w[i]]+v[i])//⼆维变⼀维 { B[j]=B[j-w[i]]+v[i]; } } } }在背包九讲⾥⾯给出⼀个⼩tip：求恰好装满背包，初始化B[0] = 0,其他都是-∞。若是求最⼤价值，初始化B[0-N]都是0。完全背包问题：多了个任何物体都可以⽆限⽤的条件。⼆维数组：（与01背包问题不同在代码⾥标出）void FindMax()//动态规划 { int i,j; //填表 for(i=1;i<=number;i++) { for(j=1;j<=capacity;j++) { if(jV[i][j-w[i]]+v[i])//不装价值⼤ { V[i][j]=V[i-1][j]; } else//这⾥与01有不同之处，其他⼀样 { V[i][j]=V[i][j-w[i]]+v[i]; } } } } }⼀维数组：(跟01背包有点不同是正着来，切从w[i]开始)void FindMaxBetter()//优化空间后的动态规划 { int i,j; for(i=1;i<=number;i++) { for(j=w[i];j<=capacity;j++) { if(B[j]<=B[j-w[i]]+v[i])//⼆维变⼀维 { B[j]=B[j-w[i]]+v[i]; } } } }

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

01背包问题，完全背包问题的⼆维数组，⼀维数组的解答关于01背包问题，完全背包问题，这⾥就不过多阐述。这⾥只是总结⼀下这两个问题的⼆维数组，⼀维数组的两种表达⽅式。为什么要⽤⼀位数组，两个原因：1.节约空间（⼆维变⼀维）2.时间复杂度降为线性。直接上代码，如果对01背包问题，完全背包问题有问题的推荐看⼀下《背包九讲》和其他博客。1. 背包九讲：2. 01背包问题可视化的⽹站：（这个是真的好⽤，你只要输⼊条件就给你画出所有的情况）3. 挺详细的⼀个博客：切⼊正题，进⾏代码总结：01背包问题：⼆维数组：void FindMax()//动态规划 { int i,j; //填表 for(i=1;i<=number;i++) { for(j=1;j<=capacity;j++) { if(jV[i-1][j-w[i]]+v[i])//不装价值⼤ { V[i][j]=V[i-1][j]; } else//前i-1个物品的最优解与第i个物品的价值之和更⼤ { V[i][j]=V[i-1][j-w[i]]+v[i]; } } } } }⼀维数组： void FindMaxBetter()//优化空间后的动态规划 { int i,j; for(i=1;i<=number;i++) { for(j=capacity;j>=w[i];j--) { if(B[j]<=B[j-w[i]]+v[i])//⼆维变⼀维 { B[j]=B[j-w[i]]+v[i]; } } } }在背包九讲⾥⾯给出⼀个⼩tip：求恰好装满背包，初始化B[0] = 0,其他都是-∞。若是求最⼤价值，初始化B[0-N]都是0。完全背包问题：多了个任何物体都可以⽆限⽤的条件。⼆维数组：（与01背包问题不同在代码⾥标出）void FindMax()//动态规划 { int i,j; //填表 for(i=1;i<=number;i++) { for(j=1;j<=capacity;j++) { if(jV[i][j-w[i]]+v[i])//不装价值⼤ { V[i][j]=V[i-1][j]; } else//这⾥与01有不同之处，其他⼀样 { V[i][j]=V[i][j-w[i]]+v[i]; } } } } }⼀维数组：(跟01背包有点不同是正着来，切从w[i]开始)void FindMaxBetter()//优化空间后的动态规划 { int i,j; for(i=1;i<=number;i++) { for(j=w[i];j<=capacity;j++) { if(B[j]<=B[j-w[i]]+v[i])//⼆维变⼀维 { B[j]=B[j-w[i]]+v[i]; } } } }