0/1背包问题
题目
描述
有N个物品，每个物品的价值di和重量wi，背包容量为M，每个物品最多可以装入背包一个，求背包可以装的物品的总价值
公式
dp[j] = dp[j] > dp[j - v[i].weight] + v[i].desirability
? dp[j] : dp[j - v[i].weight] + v[i].desirability;
动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| #include <iostream>
#include <vector>
using namespace std;
struct charm
{
int weight;
int desirability;
};
int CharmBracelet(vector<charm>& v, int n, int m)
{
vector<int> dp(m + 1);
dp[0] = 0;
for (int i = 0; i < n; i++)
{
for (int j = m; j >= v[i].weight; j--)
{
dp[j] = dp[j] > dp[j - v[i].weight] + v[i].desirability
? dp[j] : dp[j - v[i].weight] + v[i].desirability;
}
}
return dp[m];
}
int main()
{
int n, m;
cin >> n >> m;
vector<charm> v(n);
for (int i = 0; i < n; i++)
{
cin >> v[i].weight;
cin >> v[i].desirability;
}
int result = CharmBracelet(v, n, m);
cout << result << endl;
return 0;
}
|