题目描述
有 $N$ 种物品和一个容量是 $V$ 的背包,每种物品都有无限件可用。
第 $i$ 种物品的体积是 $v_i$,价值是 $w_i$。
求解将哪些物品装入背包,可使这些物品的总体积不超过背包容量,且总价值最大。
输出最大价值。
输入格式
第一行两个整数,$N$,$V$,用空格隔开,分别表示物品种数和背包容积。
接下来有 $N$ 行,每行两个整数 $v_i$,$w_i$,用空格隔开,分别表示第 $i$ 种物品的体积和价值。
输出格式
输出一个整数,表示最大价值。
数据范围
$0<N,V\le 1000$,
$0<v_i,w_i\le 1000$
输入样例
4 5
1 2
2 4
3 4
4 5
输出样例
10
思路
状态表示相同,即f[i][j]
表示选到第i
个物品的时候,总体积不超过j
的最大价值。
关键是如何计算f[i][j]
。我们可以分成三种情况来考虑:
- 不拿当前的物品,即
f[i-1][j]
。 - 第一次拿当前的物品,即
f[i-1][j-v[i]]+w[i]
。 - 已经拿过当前的物品,再拿一次,即
f[i][j-v[i]]+w[i]
。
所以总的来说,f[i][j]=max({f[i-1][j], f[i-1][j-v[i]]+w[i], f[i][j-v[i]]+w[i]]})
。
就优化的角度来看,我们可以看到,如果考虑f[i][j-v[i]]+w[i]
之后再考虑f[i-1][j]
,就会发觉这实际上就是f[i-1][j-v[i]]+w[i]
,也就是说考虑了第一个和第三个状态之后,第二个状态自然也包括了,所以可以忽略掉。
所以优化了之后,f[i][j]=max({f[i-1][j], f[i][j-v[i]]+w[i]]})
。
C++ 朴素代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n, V, v[N], w[N], 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=0; j<=V; j++) {
f[i][j]=f[i-1][j];
if (j>=v[i]) f[i][j]=max({f[i][j], f[i-1][j-v[i]]+w[i], f[i][j-v[i]]+w[i]});
}
cout<<f[n][V];
return 0;
}
C++ 优化代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n, V, v[N], w[N], 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=0; 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];
return 0;
}
C++ 终极优化代码
#include <bits/stdc++.h>
using namespace std;
const int N=1010;
int n, V, v[N], w[N], 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];
return 0;
}