算法设计实例教程 配套课件.ppt

对于状态方程的一项dp[i-1][j-w[i]]+value[i]，可以明确j-w[i]j。因为考虑物体i时需要更新的dp[j]（即dp[i][j]）需要通过dp[i-1][j-w[i]]来计算。为了保证使用的dp[j-w[i]]是仅考虑完第i-1个物体时候的值，所以dp[j-w[i]]的值更新要发生在dp[j]之后。又因为j-w[i]j，所以dp[j]需要逆序更新。如果是顺序更新，那么容量为j-w[i]和容量为j两种情况下，很有可能会放进同一个物体两次只要该物体的容量比j-w[i]还小，所以不符合这个背包问题的约束。7.3.3滚动数组intvolumn,numItem;intweights[numItem+1],value[numItem+1];//初始化背包总容量volumn，物体种数numItem，物体重量数组weights，物体价值数组valueintdp[numItem+1][volumn+1];//初始化dp全为0for(inti=1;i=numItem;i++)//对于背包容量j小于物体容量weights[i]的情况不需要考虑for(intj=volumn;j=weight[i];j++){dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}}returndp[numItem][volumn];//背包最大价值在之前的二维数组实现里面，有一个if的判断，if(jweights[i]){dp[i][j]=dp[i-1][j];}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-weights[i]]+value[i]);} 滚动数组实现中，由于在考虑物体i时，dp[j]不更新则保留了考虑物体i-1时候的状态，所以这里的判断可以转化成滚动数组实现里面的j从volumn递减到weight[i]为止即可。。7.3.3滚动数组时间限制：1000ms内存限制：32MB问题描述仓库最近新入库了很多物资，原有的警犬不够了，需要新买入一批警犬。负责人Angel发现黑心商人Demon那里一共有3种警犬，德国牧羊犬、苏格兰牧羊犬和拉布拉多。价格分别为a、b、c元一批，每种警犬都可以购买很多批，Angel的预算只有w元，这个时候就需要我们来帮忙计算一下了，如何采购警犬，才能使所剩下的钱最少？????输入说明多组数据，每组数据一行，分别为w,a,b,c(0w300000,100a,b,c300000)输出说明每组数据输出一行，为剩下的最少钱数输入样例1000050030020010000300300300输出样例01007.4动态规划应用举例1--仓库的警犬7.4动态规划应用举例1--仓库的警犬参考代码#includestdio.h#includestdlib.hintmain(){intn,x,y,z,a,b,c,min;while(scanf(%d%d%d%d,n,a,b,c)!=EOF){min=n;for(x=0;x=n/a;x++)for(y=0;y=(n-a*x)/b;y++)for(z=0;z=(n-a*x-b*y)/c;z++){min=min=(n-(a*x+b*y+c*z))?min:n-(a*x+b*y+c*z);}printf(%d\n,min);}return0;}时间限制：1000ms内存限制：32MB问题描述在战场上，指挥官TangFei要指挥我方炮火对敌军阵地马上要进行火力打击，但是我们的炮弹总数只有C枚，敌军阵地共有N个目标可以轰炸，经过作战评估，我军对每一个目标i都有一个价值（表示这个目标的重要程度）为Vi，摧毁每个目标需要的炮弹数为Pi，问如何分配活力，使得火力打击所摧毁的目标的总价值为最大？（例如，我方共有100枚炮弹，A目标需要60枚炮弹，价值100，B目标需要30枚炮弹，价值50，C目标需要80枚炮弹，价值130，显然攻击A和B目标是最佳的分配方案）