陈柏诚 • 2年前
//用二进制来优化多种背包
#include<bits/stdc++.h>
using namespace std;
int dp[201],c[500],w[500];
//数组c是用来存转化为0/1背包的重量的,w数组是价值
//数组dp就是相当于0/1背包重量为x时的最大价值
int main()
{
int V,N,count=0,i,j;//count是用来做数组的下标
cin>>V>>N;
for(i = 1; i <= N; i++)
{
int C,W,co;
cin>>C>>W>>co;
//根据LHN所讲的思维方法将多重背包转化成0/1背包
for(j = 1; j <= co; j<<=1)//枚举1、2、4、6······
{
//不断转化成0/1背包
c[count]=j*C;
w[count]=j*W;
count++;
co-=j;
}
//此时的co相当于上述的d
if(co>0)
{
//剩余的也转化成0/1背包
c[count]=co*C;
w[count++]=co*W;//这里count还要加加,因为第31行是 "<count"
}
}
for(i = 0; i < count; i++)
{
for(j = V; j >= c[i]; j--)
dp[j] = max(dp[j],dp[j - c[i]] + w[i]);
}
cout<<dp[V];
return 0;
}
cin>>w>>c>>n;
for(int i=0;i<n;i++)
{
pos++
W[pos]=w;
C[pos]=c;
}
#include<bits/stdc++.h>
using namespace std;
int w[100005],v[100005],dp[100005];
int main(){
int n,m,pos=0;
cin>>n>>m;
for(int i=1;i<=n;i++){
int a,b,c;
cin>>a>>b>>c;
for(int j=1;j<=c;j++){
pos++;
w[pos]=a;
v[pos]=b;
}
}
for(int i=1;i<=pos;i++){
for(int j=m;j>=w[i];j--) {
dp[j]=max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout<<dp[m]<<endl;
return 0;
//原作者少年Q
}
评论: