题目描述
- 完全背包问题
样例
有 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
闫氏DP方法
#include <bits/stdc++.h>
using namespace std;
const int N = 1010, V = 1010;
int f[N][V];
int n, bag_v, v, w;
int main()
{
cin >> n >> bag_v;
for(int i = 1; i <= n; i++)
{
cin >> v >> w;
for(int j = 0; j <= bag_v; j++)
{
f[i][j] = f[i - 1][j];
if( j >= v) f[i][j] = max(f[i][j], f[i][j - v] + w); //与01背包问题的差距就在这里
//还是分为n个情况,第i的时候不取,或者第i的时候取一次、两次到n-1次,然后比较这些情况的最大值。
//,这个完全背包问题:物品可以取无限次,所以取得时候又分为只取一次,两次。。。。(范围合适即可)
//f[i][j] = max(f[i-1][j,f[i-1][j-v]+w, f[i-1][j-2v]+2w, ... ,)
//f[i][j-v] = max(f[i-1][j-v], f[i-1][j-2v]+w ,..., f[i-1][j-j/n v] + j/n w)
//所以有f[i][j] = max(f[i - 1][j], f[i][j - v] + w)
}
}
cout << f[n][bag_v] << endl;
return 0;
}
```