广告设计公司宣传语杭州seo联盟

背包问题是一类组合优化问题，其基本形式是给定一组物品，每个物品都有一个重量和一个价值，以及一个有限的背包容量，目标是在不超过背包容量的前提下，选择物品使得背包中的物品价值最大化。动态规划是解决背包问题的常用方法，你不会已经忘了之前讲过的线性dp了吧？没有就好；忘了赶紧去复习一下

01背包

每件物品数量为1

题目：装箱问题  NC16693

代码： 

#include <iostream>
using namespace std;  
int t[35],dp[35][20010];  //dp[i][j]表示前i件物品，当箱子容量为j时的最大体积
int main()
{int v,n,i,j;cin>>v>>n;for(i=1;i<=n;i++) cin>>t[i];for(i=1;i<=n;i++){for(j=1;j<=v;j++){if(j<t[i]){              //不能放idp[i][j]=dp[i-1][j];}else{                   //取放与不放体积的最大值dp[i][j]=max(dp[i-1][j],dp[i-1][j-t[i]]+t[i]);}}}cout<<v-dp[n][v];return 0;
}

01背包的经典问题

题目：有n种物品和一个容量为v的背包，物品的重量分别为c，价值分别为w，每种物品只能选择一次，目标是在不超过背包容量的前提下，使背包中的物品价值最大化。

思路：每个物品都有两种选择：选与不选。无序变有序，依次考虑前1、2、3……个物品，背包容量本也是连续状态。定义dp[i][j]表示前 i 件物品，在背包容量为 j 时的最大价值。

代码：

#include <iostream>     
using namespace std;
int dp[100][100];      
int main()
{int n,v,i,j;int c[100],w[100];for(i=1;i<=n;i++) cin>>c[i];for(i=1;i<=n;i++) cin>>w[i];for(i=1;i<=n;i++){            //遍历每件物品for(j=1;j<=v;j++){        //遍历可能的背包容量if(j<c[i]){           //第i件物品放不下dp[i][j]=dp[i-1][j];}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-c[i]]+w[i]);  //不放与放取最大值}}}cout<<dp[n][v];return 0;
}

还可以用一维数组优化空间（时间复杂度还是一样，都是n*v），每次都在同一个一维数组上操作

代码：

#include <iostream>
using namespace std;
int dp[100];       //dp[j]表示前i件物品,在容量为j时的最大价值   
int main()
{int n,v,i,j;int c[100],w[100];for(i=1;i<=n;i++) cin>>c[i];for(i=1;i<=n;i++) cin>>w[i];for(i=1;i<=n;i++){             //遍历每件物品for(j=v;j>=c[i];j--){      //！！！注意注意！！！从大到小遍历背包容量（j<c[i]肯定不能放i，还是上一次结果）dp[j]=max(dp[j],dp[j-c[i]]+w[i]);  //每件物品不放就还是dp[j],放则是dp[j-c[i]]+w[i]}}cout<<dp[v];return 0;
}

下面解释从小到大遍历背包容量的错误性，假定背包容量v=10，有一重量为5的价值为1的物品。dp[5]=1，而当j=10时，dp[10]=max(dp[10]，dp[10-5]+w)=2，可以发现该物品被放了2次，而每种物品只有一件，所以错误。而从大到小遍历，若不放当前物品，则dp为上一次值，若放，dp为dp[j-c[i]]+w[i]，而dp[j-c[i]]还没遍历到，还是上一次值，所以处理没问题。

题目：开心的金明  NC16666

代码： 

#include <iostream>
using namespace std; 
int v[30],w[30],dp[30][30010];  //dp[i][j]表示前i个物品，总钱数为j时的乘积总和最大值
int main(){ int n,m,i,j;cin>>n>>m;for(i=1;i<=m;i++) cin>>v[i]>>w[i];for(i=1;i<=m;i++){for(j=1;j<=n;j++){if(j<v[i]){          //买不了idp[i][j]=dp[i-1][j];}else{dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+v[i]*w[i]);}             //取不买与买的最大值}}cout<<dp[m][n];return 0;
}

怎么样？是不是觉得 so easy呀哈哈哈哈 ，you get it !

噢对了，补充一个小tips，一开始我打代码的时候忘了写return 0，是后面补上去的，不知道大家在代码的最后写“return 0”是因为别人都写所以我也写，还是……反正驻波是第一类（捂脸）。但现在我知道了，这应该算是一种代码规范，可以用来检查程序是否正常退出，如下图（return value 0），若程序正常退出，编译器最后则会返回值 0 ，大家要从“小”开始养成代码规范o

完全背包

每种物品可以无限次选择

题目我就修改一下 “ 01背包的经典问题 ” 来引入

题目：有n种物品和一个容量为v的背包，物品的重量分别为c，价值分别为w，每种物品可以选择无限次，目标是在不超过背包容量的前提下，使背包中的物品价值最大化

思路：在01背包的一维数组优化空间解法中，我提到 “ ！注意注意！从大到小遍历背包容量 ”，以此来防止重复多次放入同一物品，而完全背包刚好就是可以重复选择同一物品来使价值最大化，那么我们从小到大遍历背包容量则就满足完全背包题目的目标了

代码：

#include <iostream>
using namespace std;
int c[100],w[100],dp[100];   //dp[j]表示前i件物品，背包容量为j时的最大价值
int main(){ int n,v,i;cin>>n>>v;for(i=1;i<=n;i++) cin>>c[i];for(i=1;i<=n;i++) cin>>w[i];for(i=1;i<=n;i++){for(j=c[i];j<=v;j++){dp[j]=max(dp[j],dp[j-c[i]]+w[i]);}}cout<<dp[v];return 0;
}

题目：货币系统  NC21467

思路： （n,a）可以表示出的金额，（m,b）也要可以表示出，而（n,a）中一种面值的货币如果可以由此系统中的其他货币组合而来，那么它就是可有可无的，我们删除尽可能多的系统中能被表示出的面值，则剩下的就是最小的m。每一种货币有无穷张则就是完全背包问题

代码：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
int a[110],dp[25000];  //dp[i]标记i是否能被其它面值表示出
int main(){ int T,n,i,j;cin>>T;while(T--){int c=0;  //计数能被表示出的面值数memset(dp,0,sizeof(dp));   //初始化dpcin>>n;for(i=1;i<=n;i++) cin>>a[i];sort(a+1,a+1+n);   //面值从小到大排序dp[0]=1;   //0肯定能被表示出for(i=1;i<=n;i++){  //遍历a中面值if(dp[a[i]]){   //该面值能被表示出c++;continue;   }for(j=a[i];j<=a[n];j++){ //若当前值不能被表示出，更新dp数组，遍历后面的所有面值if(dp[j-a[i]]){      //j可以被a[i]+j-a[i]表示出dp[j]=1;}}}cout<<n-c<<endl;}return 0;
}

多重背包

每种物品最多选择 c 个

思路：O(n^3)的循环

代码： 

#include <iostream>
using namespace std;
int dp[110][110];  //dp[i][j]表示考虑前i种物品时，背包承重为j的最大价值
int main(){ int n,T,x,w,v;cin>>n>>T;for(int i=1;i<=n;i++){     //遍历每种物品cin>>x>>w>>v;for(int j=1;j<=T;j++){ //遍历背包承重dp[i][j]=dp[i-1][j];  //若不选第i种物品for(int k=1;k<=x;k++){  //遍历i物品的选择数量if(k*w<=j){         //若背包放得下k个i物品dp[i][j]=max(dp[i][j],dp[i-1][j-k*w]+k*v);}}}}cout<<dp[n][T];return 0;
}

我后面去看题解，很多大佬都是通过二进制拆分和动态规划结合，来高效地求解多重背包问题，上面代码在数据量较大时很容易时间超限，所以还是要学一学别人先进的做法。

思路：假设我们有1种物品，数量为13，重量为2，价值为3。如果不进行二进制拆分，我们需要处理13个相同的物品。但是，通过二进制拆分，我们可以将这13个物品拆分为：13==1+2+4+6 

• 1个物品，重量为2，价值为3

• 2个物品，重量为4，价值为6

• 4个物品，重量为8，价值为12

• 6个物品，重量为12，价值为18

这样，我们只需要处理4个不同的物品，而不是13个相同的物品。在动态规划中，我们将这4个物品分别视为独立的01背包问题，再配合一维数组优化，从而大大优化了时间和空间。

代码：

#include <iostream>
using namespace std;
int w1[1010],v1[1010],dp[110];     //注意拆分后的物品种数会>n
int main(){                        //dp[j]表示背包容量为j时的最大价值int n,t,i,j,x,w,v;cin>>n>>t;int c=0;                       //记录拆分后的物品种数for(i=0;i<n;i++){int k=1;                   //每种物品从1开始拆分，而后每次*2cin>>x>>w>>v;            while(k<=x){c++;w1[c]=k*w,v1[c]=k*v;    //记录拆分后每种物品的w和vx-=k;k*=2;}if(x){                     //若最后还有剩余，将最后x个物品作为一种物品c++;w1[c]=x*w,v1[c]=x*v;}}for(i=1;i<=c;i++){             //同01动态规划的一维数组优化解法for(j=t;j>=w1[i];j--){dp[j]=max(dp[j],dp[j-w1[i]]+v1[i]);  }}cout<<dp[t];return 0;
}

分组背包

给定 n 组物品，第 i 组物品包含若干个物品，每个物品的重量和价值不同，每组最多只能选择一个物品。

题目：金明的预算方案  NC16671

思路： 每个主件最多有2个附件，那么可以将每个主件与其附件看作一个物品组，每个物品组里有

• 只有一个主件

• 一个主件+第一个附件

• 一个主件+第二个附件

• 一个主件+第一个附件+第二个附件

这四个物品，每个物品组只能选一个物品。题目就是分组背包的形式了，分组背包解法：定义 dp[j] 表示在背包容量为 j 时的最大价值（一维数组优化），对于每组物品，尝试选择该组中的每一个物品（或不选择任何物品），更新 dp 数组

代码：

#include <iostream>
#include <vector>
using namespace std;
pair<int,int>a[60];           //存储每组主件的v,w
vector<pair<int,int> >b[60];  //存储每组主件的附件v,w  （二维数组）
int dp[32010];                //存储前i件物品,总钱数为j时价格*重要度的最大值
int main(){                       int n,m,i,v,w,p;cin>>n>>m;for(i=1;i<=m;i++){        //遍历所有物品cin>>v>>w>>p;w=v*w;                //更新重要度为价格*重要度if(p==0){             //是主件a[i]={v,w};}else{b[p].push_back({v,w});  //加入所属主件的附件列表}}for(i=1;i<=m;i++){        //遍历所有物品if(a[i].first==0) continue;  //没有主件for(int j=n;j>=a[i].first;j--){         //从大到小遍历总钱数dp[j]=max(dp[j],dp[j-a[i].first]+a[i].second);  //只有一个主件if(b[i].size()==1){     //只有一个附件if(j>=a[i].first+b[i][0].first)  //可以买主件+附件dp[j]=max(dp[j],dp[j-a[i].first-b[i][0].first]+a[i].second+b[i][0].second);}if(b[i].size()==2){if(j>=a[i].first+b[i][0].first) //可买主件+第一件附件dp[j]=max(dp[j],dp[j-a[i].first-b[i][0].first]+a[i].second+b[i][0].second);if(j>=a[i].first+b[i][1].first)dp[j]=max(dp[j],dp[j-a[i].first-b[i][1].first]+a[i].second+b[i][1].second);if(j>=a[i].first+b[i][0].first+b[i][1].first)dp[j]=max(dp[j],dp[j-a[i].first-b[i][0].first-b[i][1].first]+a[i].second+b[i][0].second+b[i][1].second);}}}cout<<dp[n];return 0;
}

我写得可能有些冗长了，大家有好的想法欢迎交流！