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

背包九讲系列1——01背包、完全背包、多重背包我在进⾏⼀些互联⽹公司的技术笔试的时候，对于我来说最⼤的难题莫过于最后的那⼏道编程题了，这对算法和数据结构有⼀定程度上的要求，⽽“动态规划”⼜是编程题中经常出现的算法类型，并且对于我这种没有搞过ACM竞赛的菜鸟来说，那更是⾮常难受。以⾄于很难通过笔试，所以打算好好的学习⼀下“动态规划”这个部分，就找到了动态规划的经典⼊门，背包9讲来学习和参考。背包9讲在⽹上也是有⼀定影响⼒的⽂章，是崔添翼⼤神的作品。我将分3 次，⼀次三讲，对⽂章中我认为可能不好理解的部分，再具体化⼀些并把实现代码发布上来。进⼊主题吧1 01背包问题1.1 题⽬有N 件物品和⼀个容量为V 的背包。放⼊第i 件物品耗费的费⽤是Ci，得到的价值是Wi。求解将哪些物品装⼊背包可使价值总和最⼤。1.2 基本思路这是最基础的背包问题，特点是：每种物品仅有⼀件，可以选择放或不放。⽤⼦问题定义状态：即F[i; v] 表⽰前i 件物品恰放⼊⼀个容量为v 的背包可以获得的最⼤价值。则其状态转移⽅程便是：01背包最好理解的⽅程这个⽅程⾮常重要，基本上所有跟背包相关的问题的⽅程都是由它衍⽣出来的。所以有必要将它详细解释⼀下：“将前i 件物品放⼊容量为v 的背包中”这个⼦问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为⼀个只和前i - 1 件物品相关的问题。如果不放第i 件物品，那么问题就转化为“前i -1 件物品放⼊容量为v 的背包中”，价值为F[i - 1; v]；如果放第i 件物品，那么问题就转化为“前i - 1 件物品放⼊剩下的容量为v - Ci 的背包中”，此时能获得的最⼤价值就是F[i - 1; v - Ci] 再加上通过放⼊第i 件物品获得的价值Wi。伪代码如下：状态转移⽅程的伪代码C++代码实现：#include using namespace std;const int W=10000;const int N=100;int dp_1[N+1][W+1];int max(int a,int b){ return a>b?a:b;}int main(){ int n,w; cin>>n>>w; int *w1=new int [n]; int *v=new int [n]; int i;

for(i=0;i>w1[i]>>v[i]; } for(i=0;i=w1[0]) { dp_1[0][i]=v[0]; } else { dp_1[0][i]=0; } } for(i=1;i=w1[i]) { dp_1[i][j]=max(dp_1[i-1][j],dp_1[i-1][j-w1[i]]+v[i]); } else { dp_1[i][j]=dp_1[i-1][j]; } } }

delete [] w1; delete [] v; cout<using namespace std;const int W=10000;int dp[W+1];int max(int a,int b){ return a>b?a:b;}int main(){ int n,w; cin>>n>>w; int i,j,wi,pi; for(i=0;i>wi>>pi; if(i==0) { for(j=0;j<=w;j++) { if(j>=wi) { dp[j]=pi; } else { dp[j]=0; } } } else { for(j=w;j>=wi;j--) {

dp[j]=max(dp[j],dp[j-wi]+pi); } } } cout<>n>>w; int *w1=new int [n]; int *v=new int [n];

int i,wi,vi;

for(i=0;i>wi>>vi; w1[i]=wi; v[i]=vi; }

int j; int len=n; for(i=0;iw1[j]&&v[i]<=v[j]||w1[i]>w) { w1[i]=-1; v[i]=-1; len--; } } }

cout<<"after delete"<

int *w2=new int [len]; int *v2=new int [len];

for(i=0,j=0;i

for(i=0;i>n>>w; map m; int i,wi,vi; for(i=0;i>wi>>vi; if(wi<=w) // 费⽤⼤于w的去掉 { if((wi)!=()) { if(m[wi]::iterator it; it=(); while(it!=()) { cout<first<<" "<second<>n; while(n--) { int money; cin>>money; int i; for(i=0;i<3;i++) { for(int j=0;j<=money;j++) { if(j>=v[i]) { dp_1[j]=max(dp_1[j],dp_1[j-v[i]]+v[i]); } } } cout< 0 的最⼤整数。例如，如果Mi为13，则相应的k = 3，这种最多取13 件的物品应被分成系数分别为1、2、4、6 的四件物品。分成的这⼏件物品的系数和为Mi，表明不可能取多于Mi 件的第i 种物品。另外这种⽅法也能保证对于0 ...Mi 间的每⼀个整数，均可以⽤若⼲个系数的和表⽰。这⾥算法正确性的证明可以分0... 2^(k-1) 和2k...Mi 两段来分别讨论得出，希望读者⾃⼰思考尝试⼀下。这样就将第i 种物品分成了O(logMi) 种物品， 将原问题转化为了复杂度为O(V ∑logMi) 的01 背包问题，是很⼤的改进。下⾯给出O(logM) 时间处理⼀件多重背包中物品的过程：处理⼀件多重背包的伪代码希望你仔细体会这个伪代码，如果不太理解的话，不妨翻译成程序代码以后，单步执⾏⼏次，或者头脑加纸笔模拟⼀下，以加深理解。c++代码实现:void completePack(int dp[],int value,int weight,int total){ int i; for(i=weight;i<=total;i++) { dp[i]=max(dp[i],dp[i-weight]+value); }}void ZeroOnePack(int dp[],int value,int weight,int total){ int i; for(i=total;i>=weight;i--) { dp[i]=max(dp[i],dp[i-weight]+value); }}//多重背包问题 优化 ⼀维数组 ⼆进制的思想 时间复杂度为O(V*Σlog n[i])void mutiPack(int dp[],int value,int weight,int amount,int total){ if(weight*amount>total) { completePack(dp,value,weight,total); } else { int k=1; while(amount-k>=0) { ZeroOnePack(dp,k*value,k*weight,total); amount-=k; k*=2; } ZeroOnePack(dp,amount*value,amount*weight,total); }}int main(){ int n,w; cin>>n>>w; int i; int wi,vi,ci; for(i=0;i>wi>>vi>>ci; mutiPack(dp_1,vi,wi,ci,w); } cout<

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

背包九讲系列1——01背包、完全背包、多重背包我在进⾏⼀些互联⽹公司的技术笔试的时候，对于我来说最⼤的难题莫过于最后的那⼏道编程题了，这对算法和数据结构有⼀定程度上的要求，⽽“动态规划”⼜是编程题中经常出现的算法类型，并且对于我这种没有搞过ACM竞赛的菜鸟来说，那更是⾮常难受。以⾄于很难通过笔试，所以打算好好的学习⼀下“动态规划”这个部分，就找到了动态规划的经典⼊门，背包9讲来学习和参考。背包9讲在⽹上也是有⼀定影响⼒的⽂章，是崔添翼⼤神的作品。我将分3 次，⼀次三讲，对⽂章中我认为可能不好理解的部分，再具体化⼀些并把实现代码发布上来。进⼊主题吧1 01背包问题1.1 题⽬有N 件物品和⼀个容量为V 的背包。放⼊第i 件物品耗费的费⽤是Ci，得到的价值是Wi。求解将哪些物品装⼊背包可使价值总和最⼤。1.2 基本思路这是最基础的背包问题，特点是：每种物品仅有⼀件，可以选择放或不放。⽤⼦问题定义状态：即F[i; v] 表⽰前i 件物品恰放⼊⼀个容量为v 的背包可以获得的最⼤价值。则其状态转移⽅程便是：01背包最好理解的⽅程这个⽅程⾮常重要，基本上所有跟背包相关的问题的⽅程都是由它衍⽣出来的。所以有必要将它详细解释⼀下：“将前i 件物品放⼊容量为v 的背包中”这个⼦问题，若只考虑第i 件物品的策略（放或不放），那么就可以转化为⼀个只和前i - 1 件物品相关的问题。如果不放第i 件物品，那么问题就转化为“前i -1 件物品放⼊容量为v 的背包中”，价值为F[i - 1; v]；如果放第i 件物品，那么问题就转化为“前i - 1 件物品放⼊剩下的容量为v - Ci 的背包中”，此时能获得的最⼤价值就是F[i - 1; v - Ci] 再加上通过放⼊第i 件物品获得的价值Wi。伪代码如下：状态转移⽅程的伪代码C++代码实现：#include using namespace std;const int W=10000;const int N=100;int dp_1[N+1][W+1];int max(int a,int b){ return a>b?a:b;}int main(){ int n,w; cin>>n>>w; int *w1=new int [n]; int *v=new int [n]; int i;

for(i=0;i>w1[i]>>v[i]; } for(i=0;i=w1[0]) { dp_1[0][i]=v[0]; } else { dp_1[0][i]=0; } } for(i=1;i=w1[i]) { dp_1[i][j]=max(dp_1[i-1][j],dp_1[i-1][j-w1[i]]+v[i]); } else { dp_1[i][j]=dp_1[i-1][j]; } } }

delete [] w1; delete [] v; cout<using namespace std;const int W=10000;int dp[W+1];int max(int a,int b){ return a>b?a:b;}int main(){ int n,w; cin>>n>>w; int i,j,wi,pi; for(i=0;i>wi>>pi; if(i==0) { for(j=0;j<=w;j++) { if(j>=wi) { dp[j]=pi; } else { dp[j]=0; } } } else { for(j=w;j>=wi;j--) {

dp[j]=max(dp[j],dp[j-wi]+pi); } } } cout<>n>>w; int *w1=new int [n]; int *v=new int [n];

int i,wi,vi;

for(i=0;i>wi>>vi; w1[i]=wi; v[i]=vi; }

int j; int len=n; for(i=0;iw1[j]&&v[i]<=v[j]||w1[i]>w) { w1[i]=-1; v[i]=-1; len--; } } }

cout<<"after delete"<

int *w2=new int [len]; int *v2=new int [len];

for(i=0,j=0;i

for(i=0;i>n>>w; map m; int i,wi,vi; for(i=0;i>wi>>vi; if(wi<=w) // 费⽤⼤于w的去掉 { if((wi)!=()) { if(m[wi]::iterator it; it=(); while(it!=()) { cout<first<<" "<second<>n; while(n--) { int money; cin>>money; int i; for(i=0;i<3;i++) { for(int j=0;j<=money;j++) { if(j>=v[i]) { dp_1[j]=max(dp_1[j],dp_1[j-v[i]]+v[i]); } } } cout< 0 的最⼤整数。例如，如果Mi为13，则相应的k = 3，这种最多取13 件的物品应被分成系数分别为1、2、4、6 的四件物品。分成的这⼏件物品的系数和为Mi，表明不可能取多于Mi 件的第i 种物品。另外这种⽅法也能保证对于0 ...Mi 间的每⼀个整数，均可以⽤若⼲个系数的和表⽰。这⾥算法正确性的证明可以分0... 2^(k-1) 和2k...Mi 两段来分别讨论得出，希望读者⾃⼰思考尝试⼀下。这样就将第i 种物品分成了O(logMi) 种物品， 将原问题转化为了复杂度为O(V ∑logMi) 的01 背包问题，是很⼤的改进。下⾯给出O(logM) 时间处理⼀件多重背包中物品的过程：处理⼀件多重背包的伪代码希望你仔细体会这个伪代码，如果不太理解的话，不妨翻译成程序代码以后，单步执⾏⼏次，或者头脑加纸笔模拟⼀下，以加深理解。c++代码实现:void completePack(int dp[],int value,int weight,int total){ int i; for(i=weight;i<=total;i++) { dp[i]=max(dp[i],dp[i-weight]+value); }}void ZeroOnePack(int dp[],int value,int weight,int total){ int i; for(i=total;i>=weight;i--) { dp[i]=max(dp[i],dp[i-weight]+value); }}//多重背包问题 优化 ⼀维数组 ⼆进制的思想 时间复杂度为O(V*Σlog n[i])void mutiPack(int dp[],int value,int weight,int amount,int total){ if(weight*amount>total) { completePack(dp,value,weight,total); } else { int k=1; while(amount-k>=0) { ZeroOnePack(dp,k*value,k*weight,total); amount-=k; k*=2; } ZeroOnePack(dp,amount*value,amount*weight,total); }}int main(){ int n,w; cin>>n>>w; int i; int wi,vi,ci; for(i=0;i>wi>>vi>>ci; mutiPack(dp_1,vi,wi,ci,w); } cout<