文章
37
粉丝
68
获赞
6
访问
7.1k
#include<iostream>
using namespace std;
int dp[21][1010];
int w[21], c[21];
int main()
{
int N, V;
cin >> N >> V;//物品数量和背包的体积
for (int i = 1;i <= N;i++)
{
cin >> w[i] >> c[i];//每个物品的重量和体积
}
for (int i = 1;i <= N;i++)
{
for (int j = 0;j <=V ;j++)
{
if (j >= c[i])
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - c[i]] + w[i]);//dp[i][j]表示前i个物品背包容量最大为j最多能装的物品总重量
else
dp[i][j] = dp[i - 1][j];
}
}
cout << dp[N][V] << endl;
}
登录后发布评论
暂无评论,来抢沙发