首页下载资源后端acm常用算法模板(C++版)

ZIPacm常用算法模板(C++版)

un_fired5.57KB需要积分:1

资源文件列表:

acm常用算法模板.zip 大约有8个文件
  1. dijkstra算法.txt 1.97KB
  2. kmp.txt 493B
  3. 匈牙利算法.txt 601B
  4. 区间修改线段树.txt 2.07KB
  5. 单点修改线段树.txt 2.08KB
  6. 快速幂模板.txt 228B
  7. 最小生成树(krus).txt 1.18KB
  8. 背包.txt 2.44KB

资源介绍:

acm常用算法模板(C++版)
//01背包 #include #include int f[1010],w[1010],v[1010];//f记录不同承重量背包的总价值,w记录不同物品的重量,v记录不同物品的价值 int main(){ int t,m,i,j; memset(f,0,sizeof(f)); //总价值初始化为0 scanf("%d %d",&t,&m); //输入背包承重量t、物品的数目m for(i=1;i<=m;i++) scanf("%d %d",&w[i],&v[i]); //输入m组物品的重量w[i]和价值v[i] for(i=1;i<=m;i++){ //尝试放置每一个物品 for(j=t;j>=w[i];j--){//倒叙是为了保证每个物品都使用一次 f[j]=max(f[j-w[i]]+v[i],f[j]); //在放入第i个物品前后,检验不同j承重量背包的总价值,如果放入第i个物品后比放入前的价值提高了,则修改j承重量背包的价值,否则不变 } } printf("%d\n",f[t]); //输出承重量为t的背包的总价值 return 0; } //完全背包 #include #include using namespace std; int w[300],c[300],f[300010]; int V,n; int main() { scanf("%d%d",&V,&n); for(int i=1; i<=n; i++) { scanf("%d%d",&w[i],&c[i]); } for(int i=1; i<=n; i++) for(int j=w[i]; j<=V; j++)//注意此处,与0-1背包不同,这里为顺序,0-1背包为逆序 f[j]=max(f[j],f[j-w[i]]+c[i]); printf("max=%d\n",f[V]); return 0; } //多重背包 #include #include #include using namespace std; int dp[100007],n,m,a[105],c[105],count; void zeropack(int cost,int value) { for(int i=m;i>=cost;i--) dp[i]=max(dp[i],dp[i-cost]+value); // cout<<"01"<=m) { completepack(cost,value); return; } int k=1; while(k
100+评论
captcha