完全背包和多重背包

大家好，欢迎来到IT知识分享网。

一、完全背包

定义：有一个背包的容积为V，有N个物品，每个物品的体积为v[i]，价值为w[i]，每个物品可以取无限次放入背包中，背包所有物品价值和最大是多少？

与01背包问题的区别：

1.01背包问题里面的物品只能取1件，但是完全背包可以取无限件。

2.状态转移方程式：

01背包：

dp[i][j]=max(dp[i-1][j],dp[i-1][j-v[i]]+w[i]) //选择前i个物品，背包体积为j时的最优方案

完全背包：

dp[i][j]=max(dp[i][j-v[i]]+w[i],dp[i-1][j]) 

完全背包并不是找到上一件物品背包容量等于j-v[i]的时候,而是找到当前物品情况下j-v[i]的最大价值，因为我们物品可以无限次使用，故dp[i][j-v[i]]+w[i]的时候就是在求最大价值。

3. 完全背包问题 – AcWing题库

有 N 种物品和一个容量是 V的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N行，每行两个整数 vi,wi，用空格隔开，分别表示第 i 种物品的体积和价值。

输出格式

输出一个整数，表示最大价值。

数据范围

输入样例

4 5 1 2 2 4 3 4 4 5 

输出样例：

10

 代码

#include<stdio.h> #define N 1010 int f[N][N], v[N], w[N]; int max(int a,int b) { return a>b?a:b; } int main(){ int n, m; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i ++ ) scanf("%d%d",&v[i], &w[i]); for(int i = 1; i <= n; i ++ ) for(int j = 1; j <= m; j ++ ) { if(j<v[i]) f[i][j]=f[i-1][j]; else f[i][j] = max(f[i-1][j], f[i][j - v[i]] + w[i]); } printf("%d\n",f[n][m]); return 0; } 

二、多重背包

定义：有N种物品和一个容量为V 的背包。第i种物品最多有Ci件可用，每件耗费的空间是Vi ，价值是Wi 。求解将哪些物品装入背包可使这些物品的耗费的空间 总和不超过背包容量，且价值总和最大。

注：与完全背包相似，但是每个物品都有数量规定。

状态转移方程式：

for(int i=1;i<=n;i++) //物品数量 for(int j=1;j<=m;j++) //背包容量 for(int k=0;k<=c[i];k++) //物品选择数量 { if(j<k*v[i]) //背包容量小于这件物品的容量 dp[i][j]=dp[i-1][j]; else dp[i][j]=max(dp[i-1][j],dp[i-1][j-k*v[i]]+k*w[i]); }

有 N 种物品和一个容量是 V的背包。

第 i 种物品最多有 si件，每件体积是 vi，价值是 wi。

输入格式

第一行两个整数，N，V，用空格隔开，分别表示物品种数和背包容积。

接下来有 N 行，每行三个整数 vi,wi,si，用空格隔开，分别表示第 i 种物品的体积、价值和数量。

输出格式

输出一个整数，表示最大价值。

数据范围

输入样例

4 5 1 2 3 2 4 1 3 4 3 4 5 2 

输出样例：

10

#include<stdio.h> int v[1001],w[1001],s[1001]; int dp[1001][1001]={0}; int n,m; int max(int a,int b) { return a>b?a:b; } int main() { scanf("%d%d",&n,&m); for(int i=1; i<=n; i++) scanf("%d%d%d",&v[i],&w[i],&s[i]); for(int i=1; i<=n; i++) //物品数量 for(int j=1; j<=m; j++) //背包容量 for(int k=0; k<=s[i]; k++) //物品选择数量 { if(j>=k*v[i]) dp[i][j]=max(dp[i][j],dp[i-1][j-k*v[i]]+k*w[i]); } printf("%d",dp[n][m]); return 0; }