Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

背包问题模板

PigySu 2020-02-05 11:20:00 阅读数:59 评论数:0 点赞数:0 收藏数:0

0/1背包

01背包是在M件物品取出若干件放在空间为W的背包里,每件物品的体积为W1,W2至Wn,与之相对应的价值为P1,P2至Pn。01背包是背包问题中最简单的问题。01背包的约束条件是给定几种物品,每种物品有且只有一个,并且有权值和体积两个属性。在01背包问题中,因为每种物品只有一个,对于每个物品只需要考虑选与不选两种情况。如果不选择将其放入背包中,则不需要处理。如果选择将其放入背包中,由于不清楚之前放入的物品占据了多大的空间,需要枚举将这个物品放入背包后可能占据背包空间的所有情况。

 #include<bits/stdc++.h>
using namespace std;

const int num = ???;
 int t, n, m;// t组数据,n个物品,m背包容量
int v[num], w[num];// wi体积,vi价值
int dp[num];

int ans(){
 //初始化 
for(int i=; i<num; ++i) dp[i] = ;

for(int i=; i<=n; ++i)//第i个物品 
for(int j=m; j>=w[i]; --j)//j为体积 !!倒序 
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

return dp[m];
 }

int main(){
 scanf("%d", &t);
 while(t--){
 scanf("%d %d", &n, &m);
 for(int i=; i<=n; ++i) scanf("%d", v+i);
 for(int i=; i<=n; ++i) scanf("%d", w+i);
 printf("%d\n", ans());
  }
 return ;
 }
View Code

完全背包

有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是c,价值是w。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。

 #include<bits/stdc++.h>
using namespace std;

const int num = ???;
 int t, n, m;
 int w[num], v[num];
 int dp[num];

int fullans(){
 //初始化 
for(int i=; i<num; ++i) dp[i] = ;

for(int i=; i<=n; ++i)//第i个物品 
for(int j=w[i]; j<=m; ++j)//j为体积 !!顺序 
dp[j] = max(dp[j], dp[j-w[i]]+v[i]);

return dp[m];
 }

int main(){
 scanf("%d", &t);
 while(t--){
 scanf("%d %d", &n, &m);
 for(int i=; i<=n; ++i) scanf("%d", w+i);
 for(int i=; i<=n; ++i) scanf("%d", v+i);
 printf("%d\n",fullans());
  }
 return ;
 }
View Code

多重背包

N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件费用是c[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的费用总和不超过背包容量,且价值总和最大。

 d#include<bits/stdc++.h>
using namespace std;

const int N = ???;
 int V, m;
 int dp[N];
 int w[N], num[N];

void mul(int n,int w){
 if(n*w >= V){
 for(int i=w; i<=V; i++)
 dp[i] = max(dp[i], dp[i-w]+w);
 return ;
  }
 int k = ;
 int nC = n;
 while(k < nC){//01背包,做简单的优化
for(int i=V; i>=k*w; i--)
 dp[i] = max(dp[i], dp[i-k*w]+k*w);
 nC -= k;
 k *= ;
  }
 for(int i=V; i>=nC*w; i--)
 dp[i] = max(dp[i], dp[i-nC*w]+nC*w);
 }
 int main(){
 while(scanf("%d %d", &m, &V) && m && V){
 for(int i=; i<=V; ++i) dp[i] = ;
 for(int i=; i<m; ++i) scanf("%d", w+i);
 for(int i=; i<m; ++i) scanf("%d", num+i);

//多重背包 
for(int i=; i<m; ++i)
  mul(num[i], w[i]);

printf("%d\n",dp[V]);
  }
 return ;
 }
View Code

 

版权声明
本文为[PigySu]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/0424lrn/p/12262880.html