【POJ3624】【POJ1384】【POJ1014】01背包，完全背包，多重背包

01背包，poj3624，板子题上AC代码

#include#include#includeusing namespace std;int f[12890];int w[3405],d[3405];int main(){memset(f,0,sizeof(f));int n,m;cin>>n>>m;for(int i=1;i<=n;i++){cin>>w[i]>>d[i];}for(int i=1;i<=n;i++)for(int j=m;j>=w[i];j--){f[j]=max(f[j],f[j-w[i]]+d[i]);}sort(f+1,f+m+1);cout<<f[m]<<endl;return 0;}

完全背包，板子题，不过这个需要初始为无穷大，因为这个求最小，初始d[0]=0;
poj1384
AC代码如下：

#include#include#includeusing namespace std;int f[10005],p[505],w[505];int inf=0x3f3f3f3f;int main(){int t,e,f1,n,a,b;scanf("%d",&t);while(t--){memset(f,inf,sizeof(f));scanf("%d%d",&e,&f1);scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&p[i],&w[i]);}f[0]=0;//一开始没装物品的为0；for(int i=1;i<=n;i++)for(int j=w[i];j<=f1-e;j++){     f[j]=min(f[j],f[j-w[i]]+p[i]);}if(f[f1-e]!=inf) printf("The minimum amount of money in the piggy-bank is %d.\n",f[f1-e]);else printf("This is impossible.\n");}return 0;}

POJ1014,这道题，多重背包，但是发现，如果直接转化为01背包，会TTL,时间复杂度太大了，所以，考虑优化，二进制优化，在进行01背包选择，AC代码如下：

#include#include#includeusing namespace std;int dp[120005];int a[1000],flag=0,sum=0,cnt=0;int main(){    int s;    for(int i=1;i<=6;i++){ cin>>s; sum+=s*i; if(s) flag=1; int k=1; while(k<=s){     a[++cnt]=k*i;      //这里进行的二进制拆分     s-=k;     k*=2; } if(s){     a[++cnt]=s*i; }    }    int num=0;    while(flag){ memset(dp,0,sizeof(dp));     //一定要记得初始化； num++; dp[0]=1;//初始化一开始可以装进去 for(int i=1;i<=cnt;i++){     for(int j=sum;j>=a[i];j--)  if(dp[j-a[i]])      //状态转移方程      dp[j]=1; }    if(sum%2||!dp[sum/2]) cout<<"Collection #"<<num<<":"<<endl<<"Can't be divided."<<endl;    else cout<<"Collection #"<<num<<":"<<endl<<"Can be divided."<<endl;    cout<<endl;    sum=0;flag=0;cnt=0; //这里记得都要初始化，孩子在这犯错误了呜呜    for(int i=1;i<=6;i++){ cin>>s; sum+=s*i; if(s) flag=1; int k=1; while(k<=s){     a[++cnt]=k*i;     s-=k;     k*=2; } if(s){     a[++cnt]=s*i; }    } }    return 0;}

作业代做ddqq:3379864552