题目链接:https://www.acwing.com/problem/content/3/
题目描述
有 N 种物品和一个容量是 V 的背包,每种物品都有无限件可用。
第 i 种物品的体积是 vi,价值是 wi。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入描述
第一行两个整数,N,V,用空格隔开,分别表示物品种数和背包容积。
接下来有 N 行,每行两个整数 vi,wi,用空格隔开,分别表示第 i 种物品的体积和价值。
输出描述
输出一个整数,表示最大价值。
0<N,V≤1000
0<vi,wi≤1000
示例
输入
4 5
1 2
2 4
3 4
4 5
输出
10
分析
约定
我们记第i件物品的体积和价值为v[i],w[i]
状态表示
f(i,j)表示满足如下条件的方案的最大价值:
- 仅从前i件物品中选择
- 所选取的物品体积小于等于j
状态划分
对于f(i,j),存在两大种情况:
- 没选第i件物品
- 选了第i件物品,要考虑选了几件,1、2、3直到上限都应该考虑
状态转移方程
对应状态划分,我们便可以得到相应的状态转移方程:
- f(i,j)=f(i-1,j)
- f(i,j)=max(f[i-1][j-k*v[i]]+k*w[i]) (k*v[i]<=j,k=1,2,3----)
注意,第二行方程中的第一维为i-1,因为该种大情况将选了几件第i件物品剥离开再求和处理的。
显然,我们要取的f(i,j)应当是两大种情况的最大值,将二者形式统一,最终的状态转移方程如下:
f(i,j)=max(f(i-1,j-k*v[i])+k*w[i]) (k*v[i]<=j,k=0,1,2,3----)
优化
此时,通过状态转移方程进行编程实现需要三层循环,时间复杂度高,我们需要改进状态转移方程,以对代码做出优化。
我们可以注意到:
- f(i,j)=max(f(i-1,j),f(i-1,j-v[i])+w[i],f(i-1,j-2*v[i])+2*w[i],f(i-1,j-3*v[i])+3*w[i],---)
- f(i,j-v[i])=max(f(i-1,j-v[i]),f(i-1,j-2*v[i])+w[i],f(i-1,j-3*v[i])+2*w[i],---)
显然,我们在计算f(i,j)时可以利用f(i,j-v[i]),得到新的状态转移方程如下:
f(i,j)=max(f(i-1,j),f(i,j-v[i])+w[i]) (j-v[i]>=0)
利用该方程,我们只需要两层循环便能解决问题,时间复杂度降低。
再优化
类比0-1背包问题优化的思路:
以上,是以f(i,j)这样一个二维的函数来求解本问题的思路,我们可以想象出一张二维的表格,行对应i,列对应j,求解的过程其实就是一行一行填表的过程,不断利用之前求出的结果,最终得到最终答案。
此时我们依然可以这样考虑,对于一个f(i,j),在表中我们仅需要它正上方的元素和它左边的元素,因此采用滚动数组的思想,将原数组改为一维,减少空间开销,略微加快时间。
另外需要注意第二层循环的顺序:0-1背包问题,需要的正上方和左上方的数据,从后往前循环才不会覆盖计算新行需要的数据,但是本问题中需要的是正上方和左边的数据,必须从前往后循环。
朴素解法AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001;
int n, V;
int v[N], w[N];
int f[N][N];
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++)
{
for (int k = 0; k * v[i] <= j; k++)
{
f[i][j] = max(f[i][j], f[i - 1][j - k * v[i]] + k * w[i]);
}
}
}
cout << f[n][V] << endl;
return 0;
}
时间优化AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001;
int n, V;
int v[N], w[N];
int f[N][N];
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++)
{
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = max(f[i][j], f[i][j - v[i]] + w[i]);
}
}
cout << f[n][V] << endl;
return 0;
}
时间空间优化AC代码
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1001;
int n, V;
int v[N], w[N];
int f[N];
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[i]; j <= V; j++)
{
f[j]=max(f[j],f[j-v[i]]+w[i]);
}
}
cout << f[V] << endl;
return 0;
}
标签:方程,背包,int,max,完全,问题,物品,include
From: https://www.cnblogs.com/kongaobo/p/16963682.html