AcWing 2. 01背包问题
原题链接
简单
作者:
不易.
,
2023-12-11 19:00:18
,
所有人可见
,
阅读 115
01背包问题 ( 一维 dp )
题目背景:
现有n个物品, 每个物品对应一个价值 w[i] 和体积 v[i]
我有一个体积为 m 的背包, 我最多能装多少价值的物品?
dp算法思路:
双层循环
外层 for(i 1 - n) 内层 for(j m - v[i])
计算所有 dp[j] = 表示在所有物品中选择总体积 ≤ j 的物品总价值的最大值
计算方法:
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
d[j] = max(d[j], d[j - v[i]] + w[i]);
我的码码
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e3 + 10;
int v[N], w[N], n, m, d[N];
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for(int i = 1; i <= n; i++)
for(int j = m; j >= v[i]; j--)
d[j] = max(d[j], d[j - v[i]] + w[i]);
cout << d[m];
}