完全背包问题二维数组

通过三天的发文章，终于稍微弄明白$Markdown$了，接下来话不多说，直接干正事。
前两篇文章分别和大家讲了一下01背包的两种做法，感兴趣的可以去看看。
今天和大家分享一下完全背包问题的解题思路（二维数组）。
本文在写完全背包的解题方法时会与01背包做对比
题目如下：
【题目描述】
设有$n$种物品，每种物品有一个重量及一个价值。但每种物品的数量是无限的，同时有一个背包，最大载重量为$M$，今从$n$种物品中选取若干件(同一种物品可以多次选取)，使其重量的和小于等于$M$，而价值的和为最大。

【输入】
第一行：两个整数，$M$(背包容量，$M\le 200$)和N(物品数量，$N\le 30$)；

第2…N 1行：每行二个整数 W i , C i W_i,C_i Wi,Ci，表示每个物品的重量和价值。

【输出】
仅一行，一个数，表示最大总价值。

【输入样例】

10 4
2 1
3 3
4 5
7 9

【输出样例】

max=12

题目分析

【算法分析】

这道题和01背包差不多，只不过每种物品的数量变成了无限个，所以依然用动态规划算法求解。

【数据存储】

和01背包一样，m和n都是用两个变量储存即可，每个物品还是有两个值需储存，所以依然要用结构体。

【dp数组含义】

我们知道，01背包时dp[i][j]指的是第i件物品装在背包容量为j的背包里时的最大价值，那其实完全背包中dp数组的含义是 差不多的 一模一样的。

【递推公式】

很显然，物品数量变了，所以递推公式也会变。01背包时公式为dp[i][j]=max(dp[i-1][j],dp[i-1][j-s[i].w] s[i].v),那是因为当取了该物品后，该物品就没有了，就得取其它的；但完全背包它的物品数量是有无限件的，即取了该物品后仍能取该物品，但是不取时其实和01背包时的数量是一样的，都是dp[i-1][j]件，只不过取时的数量变成了dp[i][j-s[i].w] s[i].v，所以可以得出，完全背包的递推公式为：dp[i][j]=max(dp[i-1][j],dp[i][j-s[i].w ] s[i].v );
还是要注意：当背包容量（j）小于s[i].w时，dp[i][j]只能等于dp[i-1][j]

【初始化】

01背包中，背包容量为0时，该列均为0；填第一行时，背包容量（j）只要大于s[1].w，该格即为s[1].v，否则即为0.
完全背包中，背包容量为0时，该列仍为0；初始化第一行时，背包容量（j）大于s[1].w时，该格应为j/s[1].v，否则仍为0.

【填表】

和01背包一样，外一层循环循环物品，内一层循环循环背包，最后里面写上递推公式即可。
最后附上AC代码：
c :

#include <iostream>
#include <cstdio>
#include <iomanip>
#include <algorithm>
#include <string>
#include <cstring>
#include <cmath>
#include <climits>
#include <queue>
#include <stack>
#define maxn 205
using namespace std;
int m,n;
struct thing{
	int w,v;
}s[35];
int dp[35][205];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i  ){
		cin>>s[i].w>>s[i].v;
	}
	
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i  ){
		dp[i][1]=0;
	}
	for(int i=0;i<=m;i  ){
		if(i>=s[1].w )dp[1][i]=i/s[1].v;
		else dp[1][i]=0;
	}
	
	for(int i=1;i<=n;i  ){
		for(int j=1;j<=m;j  ){
			if(j<s[i].w)dp[i][j]=dp[i-1][j];
			else dp[i][j]=max(dp[i-1][j],dp[i][j-s[i].w ] s[i].v );
		}
	}
	cout<<"max="<<dp[n][m];
	return 0;
}

c语言：

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <limits.h>
#define maxn 205
int m,n;
struct thing{
	int w,v;
}s[35];
int dp[35][205];
int mymax(int x,int y){
	return x>y?x:y;
}
int main(){
	scanf("%d%d",&m,&n);
	for(int i=1;i<=n;i  ){
		scanf("%d%d",&s[i].w,&s[i].v);
	}
	
	memset(dp,0,sizeof(dp));
	for(int i=1;i<=n;i  ){
		dp[i][1]=0;
	}
	for(int i=0;i<=m;i  ){
		if(i>=s[1].w )dp[1][i]=i/s[1].v;
		else dp[1][i]=0;
	}
	
	for(int i=1;i<=n;i  ){
		for(int j=1;j<=m;j  ){
			if(j<s[i].w)dp[i][j]=dp[i-1][j];
			else dp[i][j]=mymax(dp[i-1][j],dp[i][j-s[i].w ] s[i].v);
		}
	}
	printf("%s%d","max=",dp[n][m]);
	return 0;
}`

下期预告：完全背包问题（一维数组）

这篇好文章是转载于：学新通技术网