#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=1010;
int v[N],w[N],dp[N][N];
int n, m;
int main()
{
scanf("%d%d",&n,&m);//n是物品数量,m是背包容量
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++) {
for(int j=1;j<=m;j++)
{
if(v[i] > j)
{
dp[i][j] = dp[i - 1][j];
} else
{
dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - v[i]] + w[i]);
}
}
}
printf("%d",dp[n][m]);
return 0;
}
01背包
©著作权归作者所有,转载或内容合作请联系作者
- 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
- 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
- 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
推荐阅读更多精彩内容
- 一、01背包 请参考洛谷p1048采药 1.二维dp 有 5 个药,花费时间分别是 [2,2,6,5,4],价值分...
- 我在进行一些互联网公司的技术笔试的时候,对于我来说最大的难题莫过于最后的那几道编程题了,这对算法和数据结构有一定程...
- 本文介绍了背包问题系列,主要包括: 【1】 01-背包及其应用【2】完全背包及其应用【3】多重背包 【1】01-背...
- 01背包 我这里给出的是Leetcode上对应的我写的题解和对应题。 416. 分割等和子集题解 416. 分割等...
- 问题描述 小偷深夜潜入一家珠宝店,店里有5件宝物,重量分别为W{1,3,2,4,5},对应的价值为V{200,10...