5.15ACM学习总结

ACM学习总结"/>

5.15ACM学习总结

1.01背包

有n个物品，它的价值和容量分别是vi和wi（放和不放）
（1）求最大价值f[j]=max(f[j],f[j-v[i]]+jia[i]);

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<algorithm>
using namespace std;
int max(int n,int m)
{return n>m?n:m;
}
int main()
{int t,n,m,jia[1001],v[1001],f[1001],i,j,k;scanf("%d",&t);while(t--){memset(f,0,sizeof(f));scanf("%d%d",&n,&m);for(i=0; i<n; i++)scanf("%d",&jia[i]);for(j=0; j<n; j++)scanf("%d",&v[j]);for(i=0; i<n; i++)//01背包for(j=m; j>=v[i]; j--){f[j]=max(f[j],f[j-v[i]]+jia[i]);}printf("%d\n",f[m]);}
}

2.完全背包

有n种物品，每种物品都有无数个，它的价值和容量分别是vi和wi
（1）求最大价值

memset(d,0,sizeof(d));    
for(i=1; i<=n; i++)
{for(j=w[i]; j<=m; j++){d[j]=max(d[j],d[j-w[i]]+v[i]);}
}
cout<<d[m]<<endl;

（2）（硬币问题）用以上所提供的硬币类型输出不同的方法次数组成给定的一个数dp[j]+=dp[j-v[i]];

#include <bits/stdc++.h>using namespace std;
int v[6];
int dp[100001];
int main()
{int n;v[0]=1,v[1]=5,v[2]=10,v[3]=25,v[4]=50;while(~scanf("%d",&n)){memset(dp,0,sizeof dp);/***dp[0]=1;**//这个很重要*/for(int i=0;i<5;i++)for(int j=v[i];j<=n;j++)dp[j]=dp[j-v[i]]+dp[j];//dp[j]+=dp[j-v[i]];cout <<dp[n]<<endl;}return 0;
}

有关精度溢出的改进：

#include<bits/stdc++.h>using namespace std;typedef long long ll;const int maxn=3e4+5;double n;
ll v[]={0,10000,5000,2000,1000,500,200,100,50,20,10,5};
ll s;
ll dp[maxn];int main()
{while(scanf("%lf",&n)!=EOF&&n){s=(ll)(n*100+0.5);memset(dp,0,sizeof(dp));dp[0]=1ll;for(int i=1;i<=11;i++){for(int j=v[i];j<=s;j++){dp[j]+=dp[j-v[i]];}}printf("%6.2f%17lld\n",n,dp[s]);//6和17是setw    return 0;
}

（3）完全背包+大数处理
给出两个数n和m，问在m以内的整数组成n的有多少种方法

#include<iostream>
#include<cstring>
#include<cstdio>
#include <algorithm>
using namespace std;
__int64 a[1005][105],b[1005][105],inf=1;int main()
{int n,m,k,i,j;for(int i=0;i<18;i++)inf*=10;while(cin>>n>>m&&(n&&m)){memset(a,0,sizeof(a));memset(b,0,sizeof(b));for(i=0;i<=m;i++)a[0][i]=1;//种类数赋1for(j=1;j<=m;j++){for(i=1;i<=n;i++){if(i<j){a[i][j]=a[i][j-1];b[i][j]=b[i][j-1];continue;}b[i][j] = b[i-j][j]+b[i][j-1]+(a[i-j][j]+a[i][j-1])/inf;a[i][j] = (a[i-j][j]+a[i][j-1])%inf;}}if(b[n][m])printf("%I64d",b[n][m]);printf("%I64d\n",a[n][m]);}return 0;
}

（4）储钱罐
通过全部赋值给INF，看最后那个是否改变了，如果没变就不能储存这么的钱

#include<bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
int v[550];
int w[550];
int dp[10010];
int W;
int main()
{int t,e,f,n;scanf("%d",&t);while(t--){scanf("%d%d",&e,&f);W=f-e;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%d %d",&v[i],&w[i]);}for(int i=0;i<=W;i++){dp[i]=INF;}dp[0]=0;for(int i=0;i<n;i++){for(int j=w[i];j<=W;j++){if(dp[j-w[i]]<INF)dp[j]=min(dp[j],dp[j-w[i]]+v[i]);}}if(dp[W]>=INF)printf("This is impossible.\n");elseprintf("The minimum amount of money in the piggy-bank is %d.\n",dp[W]);}return 0;
}

3.完全背包

有n种物品，每种物品都有ci个，它的价值和容量分别是vi和wi
完全背包+回溯路径

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;const int maxn=10010;
const int INF=0x3f3f3f3f;int used[maxn];
int dp[maxn];
int path[maxn];
int cnt[4];
int val[4]={1,5,10,25};int main()
{//freopen("int.txt","r",stdin);while(1){int n,sum=0;scanf("%d",&n);for(int i=0;i<4;i++){scanf("%d",&cnt[i]);sum+=cnt[i]*val[i];}memset(dp,-INF,sizeof(dp));memset(path,0,sizeof(path));path[0]=-1;dp[0]=0;if(!n&&!sum)break;for(int i=0;i<4;i++){memset(used,0,sizeof(used));for(int v=val[i];v<=n;v++){if(dp[v-val[i]]+1>dp[v]&&dp[v-val[i]]>=0&&used[v-val[i]]<cnt[i]){dp[v]=dp[v-val[i]]+1;used[v]=used[v-val[i]]+1;path[v]=v-val[i];}}}int ans[100];memset(ans,0,sizeof(ans));if(dp[n]<0){printf("Charlie cannot buy coffee.\n");}else {while(path[n]!=-1){ans[n-path[n]]++;n=path[n];}printf("Throw in %d cents, %d nickels, %d dimes, and %d quarters.\n", ans[val[0]], ans[val[1]], ans[val[2]], ans[val[3]]);}}return 0;
}