首页分享动态规划解决0

动态规划解决0

来源：花匠小妙招时间：2024-12-16 11:01

0-1背包思路把背包问题抽象化（X1，X2，…，Xn，其中 Xi 取0或1，表示第 i 个物品选或不选），Vi表示第 i个物品的价值，Wi表示第 i 个物品的体积（重量）；建立模型，即求max(V1X1+V2X2+…+VnXn)；约束条件，W1X1+W2X2+…+WnXn<capacity；定义V(i,j)：当前背包容量 j，前 i 个物品最佳组合对应的价值；最优性原理是动态规划的基础，最优性原理是指“多阶段决策过程的最优决策序列具有这样的性质：不论初始状态和初始决策如何，对于前面决策所造成的某一状态而言，其后各阶段的决策序列必须构成最优策略”。判断该问题是否满足最优性原理，采用反证法证明：

假设(X1，X2，…，Xn)是01背包问题的最优解，则有(X2，X3，…，Xn)是其子问题的最优解，

假设(Y2，Y3，…，Yn)是上述问题的子问题最优解，则理应有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V2X2+V3X3+…+VnXn)+V1X1；

而(V2X2+V3X3+…+VnXn)+V1X1=(V1X1+V2X2+…+VnXn)，则有(V2Y2+V3Y3+…+VnYn)+V1X1 > (V1X1+V2X2+…+VnXn)；

该式子说明(X1，Y2，Y3，…，Yn)才是该01背包问题的最优解，这与最开始的假设(X1，X2，…，Xn)是01背包问题的最优解相矛盾，故01背包问题满足最优性原理；

寻找递推关系式，面对当前商品有两种可能性：

第一，包的容量比该商品体积小，装不下，此时的价值与前i-1个的价值是一样的，即V(i,j)=V(i-1,j)；

第二，还有足够的容量可以装该商品，但装了也不一定达到当前最优价值，所以在装与不装之间选择最优的一个，即V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

其中V(i-1,j)表示不装，V(i-1,j-w(i))+v(i) 表示装了第i个商品，背包容量减少w(i)但价值增加了v(i)；

由此可以得出递推关系式：

1) j<w(i) V(i,j)=V(i-1,j)

2) j>=w(i) V(i,j)=max｛ V(i-1,j)，V(i-1,j-w(i))+v(i) ｝

#include<bits/stdc++.h> #define CAP 1500 #define NUM 50 using namespace std; int w[NUM]; int v[NUM]; int p[NUM][CAP]; void knapsack(int c,int n) { int jMax=min(w[n]-1,c); for(int j=0;j<=jMax;j++) p[n][j]=0; for(int j=w[n];j<=c;j++) { p[n][j]=v[n]; //cout<<p[n][j]<<endl; } for(int i=n-1;i>1;i--) { jMax=min(w[i]-1,c); for(int j=0;j<=jMax;j++) p[i][j]=p[i+1][j]; for(int j=w[i];j<=c;j++) p[i][j]=max(p[i+1][j],p[i+1][j-w[i]]+v[i]); } p[1][c]=p[2][c]; if(c>w[1]) p[1][c]=max(p[1][c],p[2][c-w[1]]+v[1]); } void traceback(int c,int n,int x[]) { for(int i=1;i<n;i++) { if(p[i][c]==p[i+1][c]) x[i]=0; else { x[i]=1; c=c-w[i]; } x[n]=(p[n][c])?1:0; } } int main() { int c,n; cin>>c>>n; int x[n]; for(int i=1;i<=n;i++) cin>>w[i]>>v[i]; knapsack(c,n); cout<<p[1][c]<<endl; traceback(c,n,x); for(int i=1;i<=n;i++) cout<<x[i]<<" "; }

12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758