普通的多重背包：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define met(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f const int maxn = 5*1e4+10; int w[100+10],p[100+10],c[100+10]; int dp[maxn]; int main() { int n,m; while(scanf("%d%d",&n,&m)!=EOF) { for(int i=0;i<n;i++) scanf("%d%d%d",&w[i],&p[i],&c[i]); met(dp,0); for(int i=0;i<n;i++) { for(int j=0;j<c[i];j++) { for(int k=m;k>=w[i];k--) dp[k]=max(dp[k],dp[k-w[i]]+p[i]); } } printf("%d\n",dp[m]); } }缺陷：对于大数据，可能会出现超时的情况。
二进制优化的多重背包：
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; #define met(a,b) memset(a,b,sizeof(a)) #define inf 0x3f3f3f3f const int maxn = 5*1e4+10; int w[100+10],p[100+10],c[100+10]; int dp[maxn]; int n,V; void ZeroOnePack(int cost,int weight)//01背包 { int v; for(v=V;v>=cost;v--) dp[v]=max(dp[v],dp[v-cost]+weight); } void CompletePack(int cost,int weight)//完全背包 { int v; for(v=cost;v<=V;v++) dp[v]=max(dp[v],dp[v-cost]+weight); } void MultiplePack(int cost,int weight,int amount)//多重背包（花费，价值，数量） { int k; if(cost*amount>=V) { CompletePack(cost,weight); return; } k=1; while(k<amount) { ZeroOnePack(k*cost,k*weight); amount=amount-k; k=k*2; } ZeroOnePack(amount*cost,amount*weight); } int main() { while(scanf("%d%d",&n,&V)!=EOF) { for(int i=0;i<n;i++) scanf("%d%d%d",&w[i],&p[i],&c[i]); memset(dp,0,sizeof(dp[0])*(V+1)); // memset(dp,-inf,sizeof(dp[0])*(V+1));dp[0]=0;（恰好装满） for(int i=0;i<n;i++) MultiplePack(w[i],p[i],c[i]); printf("%d\n",dp[V]); } }