背包问题（各种分类）

背包问题（各种分类）"/>

背包问题（各种分类）

主要写：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;}