01背包+完全背包
2023-08-20 15:04:58
发布于：浙江
0阅读
0回复
0点赞
一、背包问题的特性
背包问题与贪心的最大区别是，贪心取的为局部最优解，
而背包问题所取的是全局最优解。
贪心考虑的是如何使所获得的利益最大化或所得的物品最多。
而背包问题一般都需要考虑物品的价值和物品的所占面积。
二、01背包
01背包问题是指对于一个物品，要么拿，要么不拿。
使所拿的物品总价值最高。
对于01背包问题，我们可以有两种方法：
#include<bits/stdc++.h>
#include<fstream>
#include<cmath>
using namespace std;
int n,m;
int w[10005]; //每个物品的重量
int c[10005]; //每个物品的价值
int dp[1005][1005]; //动态数组
int main(){
cin >>m>>n;
for(int i=1;i<=n;i++){
cin >>w[i]>>c[i];
}
for(int i =1;i<=n;i++){
for(int j =0;j<=m;j++){
if(j>=w[i]){ //放的下的情况
dp[i][j]=max(dp[i-1][j],dp[i-1][j-w[i]]+c[i])；
}else{ //放不下的情况
dp[i][j]=dp[i-1][j];
}
}
}
cout <<dp[n][m];
return 0;
}
这里我们用二维数组来写。
当然还是可以再优化一下，用一维数组来写。
2.
#include<bits/stdc++.h>
#include<fstream>
#include<cmath>
using namespace std;
int n,m;
int w[10005]; //物品的重量
int c[10005]; //物品的价值
int dp[10005]; //动态数组
int main(){
cin >>m>>n;
for(int i=1;i<=n;i++){
cin >>w[i]>>c[i];
}
for(int i =1;i<=n;i++){
for(int j =m;j>=w[i];j--){
dp[j]=max(dp[j],dp[j-w[i]]+c[i]);
}
}
cout <<dp[m];
return 0;
}
三、完全背包问题
完全背包问题是指同一个物品可以拿多次，求最大的物品总值。
我们只需要在原来01背包的代码基础上做出略微的修改
#include<bits/stdc++.h>
#include<fstream>
#include<cmath>
using namespace std;
int n,m;
int w[10005];
int c[10005];
int dp[1005][1005];
int main(){
cin >>m>>n;
for(int i=1;i<=n;i++){
cin >>w[i]>>c[i];
}
for(int i =1;i<=n;i++){
for(int j =1;j<=m;j++){
if(j>=w[i]){
if(dp[i-1][j]>dp[i][j-w[i]]+c[i])dp[i][j]=dp[i-1][j];
else
dp[i][j]=dp[i][j-w[i]]+c[i];
}else{
dp[i][j]=dp[i-1][j];
}
}
}
cout <<dp[n][m];
return 0;
}
以上为全部内容（不喜勿喷）
这里空空如也
有帮助，赞一个