c++设有n 种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M ,今从n 种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M ,而价值的和为最大代码
时间: 2023-05-26 07:03:06 浏览: 51
//动态规划求解无限背包问题
#include<iostream>
using namespace std;
int max(int a,int b) //比较大小
{
return a>b? a:b;
}
int main()
{
int n,m;
cin>>n>>m;
int w[n+1],v[n+1]; //重量和价值数组,注意下标从1开始
for(int i=1;i<=n;i++) cin>>w[i]>>v[i];
int f[m+1]; //f[i]表示载重量为i时的最大价值
f[0]=0; //当载重量为0时,最大价值为0
for(int i=1;i<=m;i++) //从载重量为1开始逐个计算
{
f[i]=0; //初始化为最小值
for(int j=1;j<=n;j++) //每次选一种物品
{
if(i>=w[j])
f[i]=max(f[i],f[i-w[j]]+v[j]); //如果载重够放,选择当前物品,更新最大价值
}
}
cout<<f[m]<<endl; //输出载重量为m时的最大价值
return 0;
}
相关问题
设有n 种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为M ,今从n 种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于M ,而价值的和为最大。
这是一道经典的完全背包问题,使用动态规划可以解决。
定义一个二维数组dp[i][j]表示前i种物品,在背包容量为j的情况下,可以获得的最大价值。对于每一个物品i,可以选择不选、选择1个、选择2个……选择k个,其中k的上限为容量为j时最多能选择的数量。因为每一种物品都是无限的,所以这个上限就是j/weight[i]。
因此,状态转移方程为:
dp[i][j] = max(dp[i-1][j],
dp[i-1][j-weight[i]]+value[i],
dp[i-1][j-2*weight[i]]+2*value[i],
...,
dp[i-1][j-k*weight[i]]+k*value[i]),其中k的上限为j/weight[i]
初始状态为dp[i][0] = 0,表示背包容量为0时无法获得价值。
最终的答案为dp[n][M],即前n种物品在背包容量为M时可以获得的最大价值。
时间复杂度为O(nM^2/k),k为物品重量的平均值。如果k比较小,可以将上限k改为一个较小的值,以降低时间复杂度。
编写C++有n件物品,每件物品的重量为w[],价值为c[]。现有一个容量为V的背包,问如何选取物品放入背包,使得背包内物品的总价值最大。其中每种物品都只有一件。
这是一个经典的 01 背包问题,可以使用动态规划来解决。具体思路如下:
1. 定义状态:设 dp[i][j] 表示前 i 件物品,背包容量为 j 时的最大价值。
2. 初始化状态:dp[0][j] = 0,dp[i][0] = 0。
3. 状态转移方程:
当 j < w[i] 时,dp[i][j] = dp[i-1][j],即背包容量不足以放下第 i 件物品,只能选择不放入背包中。
当 j >= w[i] 时,dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + c[i]),即可以选择放入第 i 件物品或不放入第 i 件物品,取两者中的最大值。
4. 最终结果:dp[n][V] 即为所求,其中 n 为物品数量,V 为背包容量。
下面是C++代码实现:
```c++
int knapsack(int n, int V, int *w, int *c) {
int dp[n+1][V+1];
memset(dp, 0, sizeof(dp));
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]);
}
}
}
return dp[n][V];
}
```
其中,n 表示物品数量,V 表示背包容量,w 数组存储每件物品的重量,c 数组存储每件物品的价值。函数返回最大价值。