背包_C/C++/C#

背包

01背包

1.对体积背包

#include

using namespace std;

int main()

{

int t;cin>>t;

while(t--)

{

int n,v;cin>>n>>v;

int w[1005],v1[1005],dp[1005];

memset(dp,0,sizeof(dp));

for(int i=1;i<=n;i++)

cin>>w[i];

for(int i=1;i<=n;i++)

cin>>v1[i];

for(int i=1;i<=n;i++)

{

for(int j=v;j>=v1[i];j--)

{

dp[j]=max(dp[j],dp[j-v1[i]]+w[i]);

}

for(int i=v;~i;i--)cout<

/// dp[v] 为最大价值

}

2.对价值背包

#include

#define inf 0x3f3f3f3f

#define ll long long

using namespace std;

int dp[5005];

int weight[5005];

int value[5005];

int main()

{

int n,v,t;

cin>>t;

while(t--)

{

cin>>n>>v;

int sum=0;

memset(dp,inf,sizeof(dp));

for(int i=1; i<=n; i++)

{

cin>>value[i];

sum+=value[i];

}

for(int i=1;i<=n;i++)cin>>weight[i];

dp[0]=0;

for(int i=1; i<=n; i++)

{

for(int j=sum;j>=value[i]; j--)

{

dp[j]=min(dp[j],dp[j-value[i]]+weight[i]);

}

for(int i=sum;~i;i--)cout<

}

___________________________________________________________

sum+=weight[i];

for(1->n;i++)

{

i!=1-->sum-=weight[i];

load=max(v-sum,weight[i]);

for(v->load;j--)

{

dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);

}

___________________________________________________________

for (int i = 0; i < n; ++i)

{

for(int j=m;j>=w[i];j--)

{

if(dp[j]

{

dp[j]=dp[j-w[i]]+v[i];

if(!mark[j-w[i]])mark[j-w[i]]++;

mark[j]=mark[j-w[i]];

}

else if(dp[j]==dp[j-w[i]]+v[i])

{

if(!mark[j-w[i]])mark[j-w[i]]++;

mark[j]+=mark[j-w[i]];

}

} // 01 背包方案数

01背包第k优解

#include

#define me(a,x) memset(a,x,sizeof(a))

using namespace std;

int dp[1005][35];

signed main()

{

int t;cin>>t;while(t--)

{

int n,v,k;scanf("%d%d%d",&n,&v,&k);

int value[105],weight[105];me(dp,0);

int a[35],b[35];

for(int i=1;i<=n;i++)scanf("%d",value+i);

for(int i=1;i<=n;i++)scanf("%d",weight+i);

for(int i=1;i<=n;i++)

{

for(int j=v;j>=weight[i];j--)

{

for(int t=1;t<=k;t++)

{

a[t]=dp[j][t]; //将过程中得到的解保存到

b[t]=dp[j-weight[i]][t]+value[i]; // a,b 数组中

}

int m=1,x=1,y=1;

a[k+1]=b[k+1]=-1;

while(m<=k and (a[x]!=-1 or b[y]!=-1))

{

if(a[x]>b[y])dp[j][m]=a[x++];// 第m优解保存下来

else dp[j][m]=b[y++];

if(dp[j][m]!=dp[j][m-1])m++; // 去掉重复的解

}

}cout<

}

01背包路径

#include

#define me(a,x) memset(a,x,sizeof(a))

using namespace std;

int dp[1000005];

int path[25][10005];

int main()

{

int N,track;while(cin>>N>>track)

{

int val[track+5],wei[track+5];

me(dp,0);me(path,0);

for(int i=1;i<=track;i++)

{

scanf("%d",wei+i);

val[i]=wei[i];

}

for(int i=1;i<=track;i++)

{

for(int j=N;j>=wei[i];j--)

{

if(dp[j]

{

dp[j]=dp[j-wei[i]]+val[i];

path[i][j]=1;

}

else dp[j]=dp[j];

}

int i=track,j=N;

while(i>=1&&j>=0)

{

if(path[i][j]){cout<

}

cout<<"sum:"<

}

多重背包

#include //多重背包每件物品有限件

using namespace std;

#define me(a,x) memset(a,x,sizeof(a))

int main(int argc, char const *argv[])

{

int n,v;cin>>n>>v;

int dp[1005];me(dp,0);

int weight[1005],value[1005],count[10005];

for(int i=0;i>weight[i]>>value[i]>>count[i];

// for(int i=0;i

// {

// for(int j=v;j>=weight[i];j--)

// {

// for(int k=1;k<=count[i];k++)

// {

// if(j>=k*weight[i])

// {

// dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]);

// }

// }cout<

// for(int i=0;i

// {

// int k;

// for(int k=1;k

// {

// for(int j=v;j>=k*weight[i];j--)

// {

// dp[j]=max(dp[j],dp[j-k*weight[i]]+k*value[i]);

// }

// for(int j=v;j>=count[i]*weight[i];j--)dp[j]=max(dp[j],dp[j-count[i]*weight[i]]+count[i]*value[i]);

// }cout<

// int use[1005];dp[0]=1;//.................................3

// for(int i=0;i

// {

// me(use,0);

// for(int j=weight[i];j<=v;j++)

// {

// if(!dp[j] and dp[j-weight[i]] and use[j-weight[i]]

// {

// dp[j]=1;

// use[j]=use[j-weight[i]]+1;

// }

// for(int i=v;i>=0;i--)if(dp[i]){cout<

}

完全背包

//1.完全背包每件物品无限件 || 使得背包刚好装满

#include

using namespace std;

#define me(a,x) memset(a,x,sizeof(a))

int main(int argc, char const *argv[])

{

int n,v;cin>>n>>v;

int wei[1005],val[1005];

for(int i=0;i>wei[i]>>v[i];

int dp[1005];for(int i=0;i<=v;i++)dp[i]=-2e9+7;dp[0]=0;// 注意跑for初始化

for(int i=0;i

{

for(int j=wei[i];j<=v;j++)

{

dp[j]=max(dp[j],dp[j-wei[i]]+val[i]);

}

}cout<

}

// 2.方案数装满体积v的方案

int main(int argc, char const *argv[])

{

int n,v;cin>>n>>v;

int wei[1005];

for(int i=0;i>wei[i];

int dp[1005];me(dp,0);dp[0]=1;

for(int i=0;i

for(int j=wei[i];j<=v;j++)

dp[j]+=dp[j-wei[i]];

cout<

//若要求不超过件数c

for(int i=0;i

for(int j=wei[i];j<=v;j++)

for(int k=0;k<=c;k++)

if(j>=wei[i] and j>0)dp[j][k]+=dp[j-wei[i]][k-1];

int sum=0;

for(int i=0;i<=v;i++)sum+=dp[v][i];

}

// 3.有限件装满

int main(int argc, char const *argv[])

{

int n,v;cin>>n>>v;

int wei[1005],count[1005],use[1005];for(int i=0;i<=v;i++)dp[i]=-121323;dp[0]=0;

for(int i=0;i>wei[i]>>count[i];

for(int i=0;i

{

me(use,0);

for(int j=wei[i];j<=v;j++)

{

if(dp[j]

{

dp[j]=dp[j-wei[i]]+1;

use[j]=use[j-wei[i]]+1;

}

}dp[v]<=0?puts("no"):puts("yes");

}

完全背包路径

#include

using namespace std;

#define me(a,x) memset(a,x,sizeof(a))

int main(int argc, char const *argv[])

{

int n,v;cin>>n>>v;

int wei[1005],count[1005],use[1005],path[1005];

for(int i=0;i<=v;i++)dp[i]=-121323;dp[0]=0;

me(path,0);path[0]=-1;//退出条件

for(int i=0;i>wei[i]>>count[i];

for(int i=0;i

{

//me(use,0); // 有限件数加标记

for(int j=wei[i];j<=v;j++)

{

if(dp[j]

{

dp[j]=dp[j-wei[i]]+1;

//use[j]=use[j-wei[i]]+1;

path[j]=j-wei[i];

}

for(int t=p;path[t]!=-1;t=path[t])cout<

}

背包51ctoDP

背包

C/C++/C#相关栏目本月热门文章