背包问题(各种分类)"/>
背包问题(各种分类)
主要写:0-1背包,完全背包(硬币找零 硬币数无限制),多重背包(硬币找零 硬币数有限制),分数背包
0-1背包:有N种物品和一个容量为V的背包,每种物品只能用一次。第i种物品的体积是v[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。
完全背包:有N种物品和一个容量为V的背包,每种物品都有无限件可用。第i种物品的体积是v[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。
多重背包:有N种物品和一个容量为V的背包。第i种物品最多有n[i]件可用,每件体积是v[i],价值是w[i]。求解将哪些物品装入背包可使这些物品的体积总和不超过背包容量,且价值总和最大。
分数背包:有n个物品,第 i 个物品的重量与价值分别为w[i] 与 v[i]。背包容量为 V,如何让背包装入的物品具有更大的价值总和(物品可以取一部分)
区别:
会发现不同点在于每种背包的数量,01背包是每种只有一件,完全背包是每种无限件,而多重背包是每种有限件。这三个采用动态规划的方法来写。
分数背包与01背包问题不同点就是如果某物品无法被全部放入,则可以放入一部分,则采用贪心思想。
一. 0-1背包
二维数组代码:
#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[105][1005];//dp[i][j]表示装入i个物品后容量为j时所存的最大价值
int main()
{cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]);else dp[i][j]=dp[i-1][j];}}cout<<dp[n][V];
}
用空间优化,优化为一维数组:
注意 j 的循环必须是从大到小逆序开始的
#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[1005];//dp[j]容量为j时所存的最大价值
int main()
{cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=V;j>0;j--){if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[V];
}
二,完全背包
1,完全背包问题
二维数组代码:
与0-1背包不同之处是,状态转移方程
if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);//与0-1背包不同之处
#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[105][1005];//dp[i][j]表示装入i个物品后容量为j时所存的最大价值
int main()
{cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j>=v[i]) dp[i][j]=max(dp[i-1][j],dp[i][j-v[i]]+w[i]);//与0-1背包不同之处else dp[i][j]=dp[i-1][j];}}cout<<dp[n][V];
}
空间优化后的一维数组:
与0-1背包不同的是 注意 j 的循环为正序的
#include<bits/stdc++.h>
using namespace std;
int n,V,v[105],w[105],dp[1005];//dp[j]容量为j时所存的最大价值
int main()
{cin>>n>>V;for(int i=1;i<=n;i++){cin>>v[i]>>w[i];}for(int i=1;i<=n;i++){for(int j=1;j<=V;j++){if(j>=v[i]) dp[j]=max(dp[j],dp[j-v[i]]+w[i]);}}cout<<dp[V];
}
2,类似的 硬币找零 硬币数无限制问题
#include<bits/stdc++.h>
using namespace std;
int main()
{int n=0,c[1005],k,x,dp[1005];//dp[i]表示钱数为i所用的最少硬币数cin>>k;while(cin>>x){c[n++]=x;}for(int i=0;i<=k;i++){if(i==0) dp[i]=0;else dp[i]=999999999;}for(int i=0;i<n;i++){dp[c[i]]=1;}for(int i=0;i<n;i++){for(int j=c[i];j<=k;j++){dp[j]=min(dp[j],dp[j-c[i]]+1);}}cout<<dp[k];
}
三,多重背包
1,多重背包问题
就是多加了个循环,把n个相同物品拆开,就是0-1背包问题了
二维数组:
#include <bits/stdc++.h>
using namespace std;
int f[100][100];//状态函数f[i][j]表示第i件物品容量为j最大价值
int v[100];
int w[100];
int s[100];
int fun(int n,int m)
{for(int i=1;i<=n;i++) //物品数量 {for(int j=1;j<=m;j++) //背包容量 {for(int k=0;k<=s[i];k++) //物品数量可以选择0件,最多选择s[i]件 {if(j<k*w[i])f[i][j]=f[i-1][j];elsef[i][j]=max(f[i-1][j],f[i-1][j-k*w[i]]+k*v[i]);}}}return f[n][m];
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i]>>v[i]>>s[i];cout<<fun(n,m);return 0;
}
一维数组优化:
#include <bits/stdc++.h>
using namespace std;
int f[100];//状态函数f[i][j]表示第i件物品容量为j最大价值
int v[100];
int w[100];
int s[100];
int fun(int n,int m)
{for(int i=1;i<=n;i++){for(int j=m;j>=w[i];j--){for(int k=0;k<=s[i] && k*w[i]<=j;k++){f[j]=max(f[j],f[j-k*w[i]]+k*v[i]);}}}return f[m];
}
int main()
{int n,m;cin>>n>>m;for(int i=1;i<=n;i++)cin>>w[i]>>v[i]>>s[i];cout<<fun(n,m);return 0;
}
2,类似的 硬币找零 硬币数有限制问题
对比无限制问题,就是多了一层循环用来对硬币数目进行判断
#include<bits/stdc++.h>
using namespace std;
int main()
{int t[11],coins[11],dp[20002];int n,m;cin>>n;for(int i=0;i<n;i++){cin>>t[i]>>coins[i];}cin>>m;for(int i=1;i<=m;i++)dp[i]=9999;for(int i=0;i<n;i++){for(int j=1;j<=coins[i];j++){for(int k=m;k>=t[i];k--)dp[k]=min(dp[k],dp[k-t[i]]+1);}}cout<<dp[m];
}
四,分数背包
思想:用物品的价值除以它的容量,求出单位容量的价值p,再利用贪心思想,将p大的先装入。
#include<bits/stdc++.h>
using namespace std;
struct node
{int w,v;double p;
}a[1005];int cmp(node a,node b)
{return a.p>b.p;
}int main()
{int n,c;double ans=0;cin>>n>>c;if(n==0 || c==0) return 0;for(int i=0;i<n;i++)cin>>a[i].v;for(int i=0;i<n;i++)cin>>a[i].w;for(int i=0;i<n;i++)a[i].p=(double)a[i].v/a[i].w;sort(a,a+n,cmp);for(int i=0;i<n;i++){if(a[i].w<=c){ans+=a[i].v;c-=a[i].w;}else{ans+=a[i].p*c;break;}}cout<<ans;}
更多推荐
背包问题(各种分类)
发布评论