有N个物品,每个物品的重量是wi ,每个物品的价值是vi 。 求解当背包容量为W时,能获得的最大价值,并输出获得最大价值时每种物品是否在背包内 数据范围 0 < n <= 30 重量、价值、背包容量均为正整数用C++
时间: 2024-05-16 16:17:51 浏览: 25
可以使用 01 背包或者完全背包进行求解,这里以 01 背包为例。
1. 定义状态
我们定义 dp[i][j] 表示前 i 个物品放入容量为 j 的背包中所能获得的最大价值。
2. 状态转移方程
对于第 i 个物品,我们有两种选择:放入背包中或不放入背包中。
- 如果选择放入背包中,则背包剩余容量为 j-w[i],此时最大价值为 dp[i-1][j-w[i]] + v[i]。
- 如果选择不放入背包中,则最大价值为 dp[i-1][j]。
综上所述,状态转移方程为:dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+v[i])。
3. 初始化
当背包容量为 0 时,无论物品数量如何,背包能得到的最大价值都为 0。即 dp[i][0] = 0。
当物品数量为 0 时,无论背包容量如何,背包能得到的最大价值都为 0。即 dp[0][j] = 0。
4. 求解
最终答案为 dp[n][W],即前 n 个物品放入容量为 W 的背包中所能获得的最大价值。
5. 输出方案
我们可以在求解 dp[i][j] 的时候记录下来选择了哪些物品,从而得到最优方案。具体做法是,如果 dp[i][j] = dp[i-1][j-w[i]]+v[i],说明第 i 个物品被选择,将其标记为已选。最后从标记的物品中输出即可。
下面是示例代码:
```c++
#include <iostream>
using namespace std;
const int N = 35;
int w[N], v[N], dp[N][N];
bool g[N][N];
int main()
{
int n, W;
cin >> n >> W;
for (int i = 1; i <= n; i++) cin >> w[i] >> v[i];
for (int i = 1; i <= n; i++)
for (int j = W; j >= w[i]; j--)
{
if (dp[i-1][j] < dp[i-1][j-w[i]] + v[i])
{
dp[i][j] = dp[i-1][j-w[i]] + v[i];
g[i][j] = true;
}
else
dp[i][j] = dp[i-1][j];
}
cout << "最大价值为:" << dp[n][W] << endl;
cout << "选中的物品为:";
int j = W;
for (int i = n; i >= 1; i--)
if (g[i][j])
{
cout << i << " ";
j -= w[i];
}
cout << endl;
return 0;
}
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)