背包问题简单整理 - 君凌烟阁
hdu2546,01背包，需要有点变形，计算时需要把价格最大的菜先放一边，最后计算。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; int V; int dp[1200]; void ZeroOnePack(int ci,int wi) { for(int v=V-5;v>=ci;--v) dp[v] = max(dp[v],dp[v-ci]+wi); } int main() { //freopen("test.txt","r",stdin); int n; while(true) { scanf("%d",&n); if(n==0) break; memset(dp,0,sizeof(dp)); int vi[1200]; int iMaxIndex = 0; int iMaxVal = -10; for(int i=0;i<n;++i) { scanf("%d",&vi[i]); if(iMaxVal < vi[i]) { iMaxIndex = i; iMaxVal = vi[i]; } } scanf("%d",&V); if(V<5) { printf("%d\n",V); } else { for(int i=0;i<n;++i) if(i != iMaxIndex) ZeroOnePack(vi[i],vi[i]); printf("%d\n",V-dp[V-5]-vi[iMaxIndex]); } } return 0; }
View Code
hdu 2191 多重背包，多重背包主要可以分解成01背包和完全背包。
#include<iostream> #include<cstdio> #include<set> #include<map> #include<vector> #include<iterator> #include<algorithm> #include<cstring> using namespace std; int V,n; int dp[200]; void ZeroOnePack(int vi,int wi) { for(int v=V;v>=vi;--v) dp[v] = max(dp[v],dp[v-vi]+wi); } void CompletePack(int vi,int wi) { for(int v=vi;v<=V;++v) dp[v] = max(dp[v],dp[v-vi]+wi); } void MultiPack(int vi,int wi,int ki) { if(vi*ki >= V) { CompletePack(vi,wi); } else { for(int k=1;k<ki;k*=2) { ZeroOnePack(k*vi,k*wi); ki -= k; } ZeroOnePack(ki*vi,ki*wi); } } int main() { //freopen("test.txt","r",stdin); int c; scanf("%d",&c); while(c--) { memset(dp,0,sizeof(dp)); scanf("%d%d",&V,&n); int v[200],w[200],num[200]; for(int i=0;i<n;++i) { scanf("%d%d%d",&v[i],&w[i],&num[i]); } for(int i=0;i<n;++i) MultiPack(v[i],w[i],num[i]); printf("%d\n",dp[V]); } return 0; }
View Code
版权声明：本文为jlyg原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。