2023年8月1日发(作者：)
c++01背包、完全背包、多重背包思路+代码今天蒟蒻来给⼤家讲01背包、完全背包、多重背包的思路和代码⼀.先来区分⼀下这三种背包的区别01背包：有N件物品和⼀个容量为V的背包。（每种物品均只有⼀件）第i件物品的费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使价值总和最⼤。完全背包：有N种物品和⼀个容量为V的背包，每种物品都有⽆限件可⽤。第i种物品的费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。多重背包：有N种物品和⼀个容量为V的背包。第i种物品最多有n[i]件可⽤，每件费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。⼆、2.01背包代码+思路+优化思路：每种物品只能选择⼀次或者不选，求背包容量内的最⼤价值先给出状态转移⽅程:f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);解释⼀下：f[i][j]表⽰的是前i个物品中，背包容量为j时，得到的最⼤价值；如果在容量为j时选择不放第i个物品，那么f[i][j]=f[i-1][j],f[i-1][j]表⽰前⼀个物品在容量j时的状态值；如果在容量为j时选择放第i个物品，那么f[i][j]=f[i-1][j-w[i]]+v[i]，f[i-1][j-w[i]]+v[i]表⽰前⼀个物品得到的状态加上第i个物品的价值；So，f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);代码：#includeint n,m,v[10500],w[10500],f[1050][1050];int main(){ scanf("%d %d",&m,&n); for(int i=1;i<=n;i++)scanf("%d %d",&v[i],&w[i]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(w[i]<=j)f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); else f[i][j]=f[i-1][j]; } } printf("%d",f[n][m]); return 0;}优化还有⼀种⽤⼀维就可以AC的代码：注意;⾥⾯第⼆个循环为什么要倒着来，遍历到第i个物品时，f[j]应该与第i-1个物品的状态⽐较，如果顺着来的话，f[j]则与第i个物品的状态进⾏了⽐较，这样会出事的；#include=1;j--){ if(w[i]<=j)f[j]=max(f[j],f[j-w[i]]+v[i]); } } printf("%d",f[m]); return 0;}三、完全背包思路+代码思路：每种物品可以选⽆数次，求背包容量内的最⼤价值状态转移⽅程为：f[j]=max(f[j],f[j-w[i]]+v[i]);完全和01的差别就在于01只有两种情况：要么取，要么不取。⽽完全有多种情况：要么取，要么取1个，要么取2个，要么取三个······代码：#includeint n,m,v[10500],w[10500],f[10500];int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]); for(int i=1;i<=n;i++){ for(int j=w[i];j<=m;j++){ f[j]=max(f[j],f[j-w[i]]+v[i]); } } printf("%d",f[m]); return 0;}四、多重背包思路+代码思路：每种物品能取有限次，求背包容量内的最⼤值多重背包问题化作01背包问题解决，如果价值为v的物品有x个，则化成x个价值为v的物品；代码：#includeint n,m,v[10500],w[10500],f[10500];int main(){ scanf("%d %d",&m,&n); for(int i=1; i<=n; i++)scanf("%d %d",&v[i],&w[i],&num[i]); int k=n+1; for(int i=1; i<=n; i++){ for(int j=1; j=1; j--){ if(w[i]<=j)f[j]=max(f[j],f[j-w[i]]+v[i]); } } printf("%d",f[m]); return 0;}五、注意事项1、做题时⼀定要思考好这题能不能⽤背包因为背包推状态转移⽅程是⾮常耗时的。2、如果可以使⽤背包的话⼀定要想清楚是01还是多重还是完全。3、状态转移⽅程⼀定不能推错。好了这次就讲这么多吧！
2023年8月1日发(作者：)
c++01背包、完全背包、多重背包思路+代码今天蒟蒻来给⼤家讲01背包、完全背包、多重背包的思路和代码⼀.先来区分⼀下这三种背包的区别01背包：有N件物品和⼀个容量为V的背包。（每种物品均只有⼀件）第i件物品的费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使价值总和最⼤。完全背包：有N种物品和⼀个容量为V的背包，每种物品都有⽆限件可⽤。第i种物品的费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。多重背包：有N种物品和⼀个容量为V的背包。第i种物品最多有n[i]件可⽤，每件费⽤是c[i]，价值是w[i]。求解将哪些物品装⼊背包可使这些物品的费⽤总和不超过背包容量，且价值总和最⼤。⼆、2.01背包代码+思路+优化思路：每种物品只能选择⼀次或者不选，求背包容量内的最⼤价值先给出状态转移⽅程:f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);解释⼀下：f[i][j]表⽰的是前i个物品中，背包容量为j时，得到的最⼤价值；如果在容量为j时选择不放第i个物品，那么f[i][j]=f[i-1][j],f[i-1][j]表⽰前⼀个物品在容量j时的状态值；如果在容量为j时选择放第i个物品，那么f[i][j]=f[i-1][j-w[i]]+v[i]，f[i-1][j-w[i]]+v[i]表⽰前⼀个物品得到的状态加上第i个物品的价值；So，f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]);代码：#includeint n,m,v[10500],w[10500],f[1050][1050];int main(){ scanf("%d %d",&m,&n); for(int i=1;i<=n;i++)scanf("%d %d",&v[i],&w[i]); for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ if(w[i]<=j)f[i][j]=max(f[i-1][j],f[i-1][j-w[i]]+v[i]); else f[i][j]=f[i-1][j]; } } printf("%d",f[n][m]); return 0;}优化还有⼀种⽤⼀维就可以AC的代码：注意;⾥⾯第⼆个循环为什么要倒着来，遍历到第i个物品时，f[j]应该与第i-1个物品的状态⽐较，如果顺着来的话，f[j]则与第i个物品的状态进⾏了⽐较，这样会出事的；#include=1;j--){ if(w[i]<=j)f[j]=max(f[j],f[j-w[i]]+v[i]); } } printf("%d",f[m]); return 0;}三、完全背包思路+代码思路：每种物品可以选⽆数次，求背包容量内的最⼤价值状态转移⽅程为：f[j]=max(f[j],f[j-w[i]]+v[i]);完全和01的差别就在于01只有两种情况：要么取，要么不取。⽽完全有多种情况：要么取，要么取1个，要么取2个，要么取三个······代码：#includeint n,m,v[10500],w[10500],f[10500];int main(){ scanf("%d%d",&m,&n); for(int i=1;i<=n;i++)scanf("%d%d",&v[i],&w[i]); for(int i=1;i<=n;i++){ for(int j=w[i];j<=m;j++){ f[j]=max(f[j],f[j-w[i]]+v[i]); } } printf("%d",f[m]); return 0;}四、多重背包思路+代码思路：每种物品能取有限次，求背包容量内的最⼤值多重背包问题化作01背包问题解决，如果价值为v的物品有x个，则化成x个价值为v的物品；代码：#includeint n,m,v[10500],w[10500],f[10500];int main(){ scanf("%d %d",&m,&n); for(int i=1; i<=n; i++)scanf("%d %d",&v[i],&w[i],&num[i]); int k=n+1; for(int i=1; i<=n; i++){ for(int j=1; j=1; j--){ if(w[i]<=j)f[j]=max(f[j],f[j-w[i]]+v[i]); } } printf("%d",f[m]); return 0;}五、注意事项1、做题时⼀定要思考好这题能不能⽤背包因为背包推状态转移⽅程是⾮常耗时的。2、如果可以使⽤背包的话⼀定要想清楚是01还是多重还是完全。3、状态转移⽅程⼀定不能推错。好了这次就讲这么多吧！
发布评论