编写C++代码有n件物品,每件物品的重量为w[],价值为c[]。现有一个容量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品都只有一件。
时间: 2024-05-04 14:22:18 浏览: 26
这是一个经典的01背包问题,可以使用动态规划来解决。定义一个二维数组dp,其中dp[i][j]表示前i件物品放入容量为j的背包中所得到的最大价值。
动态转移方程为:
当第i件物品不放入背包中:dp[i][j] = dp[i-1][j]
当第i件物品放入背包中:dp[i][j] = dp[i-1][j-w[i]] + c[i]
综合上述两种情况,得到状态转移方程:
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i])
最终的答案为dp[n][V],其中n表示物品的数量,V表示背包的容量。
以下是C++代码实现:
```c++
#include <iostream>
#include <algorithm>
using namespace std;
int main()
{
int n, V;
cin >> n >> V;
int w[n+1], c[n+1];
for(int i=1; i<=n; i++)
cin >> w[i] >> c[i];
int dp[n+1][V+1];
for(int i=0; i<=n; i++)
dp[i][0] = 0;
for(int j=0; j<=V; j++)
dp[0][j] = 0;
for(int i=1; i<=n; i++)
{
for(int j=1; j<=V; j++)
{
if(j < w[i])
dp[i][j] = dp[i-1][j];
else
dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]]+c[i]);
}
}
cout << dp[n][V] << endl;
return 0;
}
```