Codeforce 106C(多重背包)

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

链接：点击打开链接

题意：有两种原料，m种面包，每种面包可以由bi克原料B和ci克原料A组成，能够产生di的价值，也可以只有c0克原料A生产，产生d0的价值，给出第A种原料N克，每种面包自带ai克原料B(只能供当前这种面包使用)，问最大产生多少价值

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int dp[20][1005];
int w[50],v[50],s[50];
int main(){int n,m,i,j,k,a,b,c,d;while(cin>>n>>m>>c>>d){w[0]=d,v[0]=n/c,s[0]=c;                 //w代表价值，v代表数量，s代表重量for(i=1;i<=m;i++){                      //因为物品不可分割，所以不能按贪心考虑，也因此想到cin>>a>>b>>c>>d;                    //dp，从而是一个多重背包s[i]=c;w[i]=d;v[i]=min(a/b,n/c);}for(i=0;i<=m;i++)for(j=0;j<=n;j++)for(k=0;k<=v[i]&&k*s[i]<=j;k++)dp[i+1][j]=max(dp[i+1][j],dp[i][j-k*s[i]]+k*w[i]);cout<<dp[m+1][n]<<endl;}return 0;
}

 

 

这篇关于Codeforce 106C(多重背包)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---