1. 问题描述
有 N 种物品和一个容量是 W 的背包，每种物品都有无限件可用。
第 i 种物品的体积是 wi，价值是 vi。
求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。
2. 输入格式
第一行两个整数，N，W，用空格隔开，分别表示物品种数和背包容积。
接下来有 N 行，每行两个整数wi，vi，用空格隔开，分别表示第 i 种物品的体积和价值。
3. 输出格式
输出一个整数，表示最大价值。
4. 数据范围
0<N,
W≤1000,
0<wi,
vi≤1000
5. 输入样例
4 5
1 2
2 4
3 4
4 5
6. 输出样例
10
7. 问题分析
8. 代码实现
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 5;//最大物品数量
int w[maxn], v[maxn], dp[maxn][maxn];//w物品重量 v物品价值 dp总价值
int main(){
int N, W;//物品种类数和最大容量
cin >> N >> W;
for(int i = 1; i <= N; ++i)//从下标1开始存储每件物品的重量和价值
cin >> w[i] >> v[i];
for(int i = 1; i <= N; ++i){
for(int j = 0; j <= W; ++j){
dp[i][j] = dp[i-1][j];//不选
if(w[i]<=j)//如果重量小于j
dp[i][j] = max(dp[i][j], dp[i][j-w[i]] + v[i]);
}
}
cout << dp[N][W] << endl;
return 0;
}
9. 优化算法
找到规律发现每次下一个只与当前行的数据有关系
状态转移方程：f[j] = max(f[j], f[j - w[i]] + v[i])
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000 + 5;//最大物品数量
int w[maxn], v[maxn], dp[maxn];//w物品重量 v物品价值 dp总价值
int main(){
int N, W;//物品种类数和最大容量
cin >> N >> W;
for(int i = 1; i <= N; ++i)//从下标1开始存储每件物品的重量和价值
cin >> w[i] >> v[i];
for(int i = 1; i <= N; ++i)
for(int j = w[i]; j <= W; ++j)
dp[j] = max(dp[j], dp[j-w[i]] + v[i]);
cout << dp[W] << endl;
return 0;
}
- ——————END-2022-03-30——————
- 个人学习笔记，如有纰漏，敬请指正。
- 感谢您的阅读。