hdu2191

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

多重背包

两种思路

一：将每件物品，无论是否相同，都作为独立的一件进行01背包，时间消耗较大。

二：转化为二进制，如5分解为1+2+3，,1分解为1+2+4+6，如此一来，对任意整数n，保证了0~n内均可由这些数组合而成，对任意物品，可以保证分解之后不影响取的所有状态，而转化以后，将n的数量转化为logn，大大降低了时间消耗。

一：

#include <iostream>using namespace std;int dp[105];
int w[105];
int v[105];
int c[105];
int n,m;int main()
{int r;cin>>r;while (r--){cin>>n>>m;memset(dp,0,sizeof(dp));memset(w,0,sizeof(w));memset(v,0,sizeof(v));memset(c,0,sizeof(c));for (int i=1;i<=m;i++)cin>>w[i]>>v[i]>>c[i];for (int i=1;i<=m;i++){for (int t=1;t<=c[i];t++){for (int k=n;k>=w[i];k--){if (dp[k]<dp[k-w[i]]+v[i])dp[k]=dp[k-w[i]]+v[i];}}}cout<<dp[n]<<endl;}
}

二：

#include <iostream>using namespace std;int dp[505];
int w[505];
int v[505];
int c[105];
int n,m;void bin()
{int count=1;for (int i=1;i<=m;i++){int t=2;while (t*2-1<=c[i]){int w1=w[i]*t;w[m+count]=w1;int v1=v[i]*t;v[m+count]=v1;count++;t=t*2;}t=t/2;if(c[i]-t*2+1>0){t=c[i]+1-t*2;int w1=w[i]*t;w[m+count]=w1;int v1=v[i]*t;v[m+count]=v1;count++;}}m=m+count-1;
}int main()
{int r;cin>>r;while (r--){cin>>n>>m;memset(dp,0,sizeof(dp));memset(w,0,sizeof(w));memset(v,0,sizeof(v));memset(c,0,sizeof(c));for (int i=1;i<=m;i++)cin>>w[i]>>v[i]>>c[i];bin();/*for (int i=1;i<=m;i++)cout<<w[i]<<" "<<v[i]<<endl;*/for (int i=1;i<=m;i++){for (int k=n;k>=w[i];k--){if (dp[k]<dp[k-w[i]]+v[i])dp[k]=dp[k-w[i]]+v[i];}}cout<<dp[n]<<endl;}
}

这篇关于hdu2191的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---