hud-2191多重背包问题

本文主要是介绍hud-2191多重背包问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

#include "stdio.h"
#include "string.h"
int p[105],h[105],c[105];  //价钱 重量 袋数
int dp[105];
int n;
void CompletePacc(int p,int h) //第i种大米价格 第i种大米重量
{int i;for(i=p;i<=n;i++)if(dp[i]<dp[i-p]+h)       {dp[i]=dp[i-p]+h;}	
}void ZeroOnePacc(int p,int h)
{int i;for(i=n;i>=p;i--)if(dp[i]<dp[i-p]+h){dp[i]=dp[i-p]+h;}
}void MultiPacc(int p,int h,int c)  //第i种大米价格 第i种大米重量 第i种大米袋数
{int k;if( p*c > n ){CompletePacc(p,h);  //第i种大米价格 第i种大米重量return;}k=1;while( k < c ){ZeroOnePacc(k*p,k*h); c-=k;k*=2;}ZeroOnePacc(c*p,c*h);}int main()
{int t;scanf("%d",&t);       //数据数while( t-- ){memset(dp,0,sizeof(dp));int m,i,j;scanf( "%d%d",&n,&m );         //经费金额 大米种类for( i=1;i<=m;i++ ){scanf("%d%d%d",&p[i],&h[i],&c[i]); //每袋价格 每袋重量 袋数}for( i=1;i<=m;i++ ){MultiPacc(p[i],h[i],c[i]);   }printf("%d\n",dp[n]);}return 0;
}

这篇关于hud-2191多重背包问题的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---