云计算百科
云计算领域专业知识百科平台

蓝桥杯19681 01背包

问题描述

有 N 件物品和一个体积为 M 的背包。第 i 个物品的体积为 vi​,价值为 wi​。每件物品只能使用一次。

请问可以通过什么样的方式选择物品,使得物品总体积不超过 M 的情况下总价值最大,输出这个最大价值即可。

输入格式

第一行输入两个正整数 N,M。(1≤N,M≤1000)

接下来 N 行,每行输入两个整数 vi,wi​。(0≤vi,wi≤1000)

输出格式

输出一个整数,表示符合题目要求的最大价值。

样例输入

4 5
1 2
2 4
3 4
4 5

样例输出

8

说明

你可以选择第二个物品和第三个物品。

 

 分别考虑前1~4个物品时,背包容量分别为1~5时的最大价值:

#include<iostream>
#include<algorithm>
using namespace std;

const int N = 1e3+10;
int n, m; //n件物品,体积为m
int v[N], w[N];
int dp[N]; //dp[j]表示背包容量为j时的最大价值

int main()
{
cin>>n>>m;
for(int i=1; i<=n; ++i) cin>>v[i]>>w[i];

for(int i=1; i<=n; ++i) //遍历每个物品
{
for(int j=m; j>=0; j–) //逆向遍历背包容量,确保每个物品只被考虑一次
{
//如果当前物品能放入
if(j>=v[i])
{
//不选当前物品:保持dp[j]不变
//选当前物品:dp[j-v[i]] + w[i]
dp[j] = max(dp[j], dp[j-v[i]] + w[i]);
}
}
}

cout<<dp[m];

return 0;
}

赞(0)
未经允许不得转载:网硕互联帮助中心 » 蓝桥杯19681 01背包
分享到: 更多 (0)

评论 抢沙发

评论前必须登录!