动态规划与其他算法比较，大大减少了计算量，丰富了计算的结果，最适合解决最优解问题。今天讲的是背包问题。
1、0-1背包：
简介：有n件物品，总空间是w,前i件的容量是w[i]，前i件的价值是v[i]，那么所获取的最大容量是dp[w].
代码如下：
#include<stdio.h> #include<string.h> int f[201000]; int w[210000]; int v[210000]; int max(int n,int m) { if(n>m) return n; else return m; } int main() { int n,m; int i,j; while(~scanf("%d%d",&n,&m)) { memset(f,0,sizeof(f)); for(i=1;i<=n;i++) scanf("%d%d",&w[i],&v[i]); for(i=1;i<=n;i++) for(j=m;j>=w[i];j--) { int s=f[j-w[i]]+v[i]; f[j]=max(f[j],s); } printf("%d\n",f[m]); } return 0; }
2、完全背包：
简介：完全背包是有n种物品，总空间为w，每种的物品的件数是无限个，已知每种物品的容量为w[i],价值为v[i]，如何满足最大价值。
代码如下：
#include <iostream> #include <algorithm> using namespace std; int a[600],b[600],dp[1000005]; int main() { int t,x,y,n; cin>>t; while(t--){ int w; cin>>w; //背包容量 cin>>n; for(int i=0;i<n;i++) cin>>b[i]>>a[i]; for(int i=0;i<=w;i++) //初始化分两种情况：1、如果背包要求正好装满则初始化 f[0] = 0, f[i]=INF;2、如果不需要正好装满 f[0~w] = 0; dp[i]=0; for(int i=0;i<n;i++) for(int j=b[i];j<=w;j++)//j表示背包容量 dp[j]=max(dp[j],dp[j-b[i]]+a[i]); // for(int i=1;i<=w;i++) cout<<dp[w]<<endl; } return 0; }
3、多重背包：
简介：多重背包就是0-1背包的扩展，0-1背包每一种物品一共有一件，多重背包每一种可能有多件，如一共有n种物品，每种物品的件数是bag[i]，总空间是w,每一件容量是w[i],每一件价值是v[i].
代码如下：
#include<iostream> #include<string.h> #include <algorithm> int v[1000],w[1000],c[1000],dp[1000]; using namespace std; int main() { int T; cin>>T; while(T--) { memset(dp,0,sizeof(dp)); int n,m; cin>>n>>m; for(int i=1;i<=m;i++) cin>>v[i]>>w[i]>>c[i]; for(int i=1;i<=m;i++) for(int k=1;k<=c[i];k++) for(int j=n;j>=v[i];j--) dp[j]=max(dp[j],dp[j-v[i]]+w[i]); cout<<dp[n]<<endl; } return 0; }
