Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 47057 | Accepted: 20017 |
Description
Bessie has gone to the mall's jewelry store and spies a charm bracelet. Of course, she'd like to fill it with the best charms possible from the N (1 ≤ N ≤ 3,402) available charms. Each charm i in the supplied list has a weight Wi (1 ≤ Wi ≤ 400), a 'desirability' factor Di (1 ≤ Di ≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M (1 ≤ M ≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
Input
* Line 1: Two space-separated integers: N and M
* Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
Output
* Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
Sample Input
4 6
1 4
2 6
3 12
2 7
Sample Output
23
解题思路:
这是一道背包问题,要求在N件物品中挑选总体积不超过j的总价值最大的物品,每一件物品都有选和不选两种状态。对每一个物品依次遍历,求每一个容积选或不选该物品后的最大价值和。即为该容积在当前个数的物品条件下所能取得的价值最大总和。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int maxn = 12880+20;
int W[maxn],D[maxn],dp[maxn];
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++){
scanf("%d%d",&W[i],&D[i]);
}
for(int k = 1;k <= n;k++){
for(int w = m;w >= W[k];w--){
dp[w] = max(dp[w],dp[w-W[k]] + D[k]);
}
}
printf("%d",dp[m]);
}
因篇幅问题不能全部显示,请点此查看更多更全内容
Copyright © 2019- esig.cn 版权所有 湘ICP备2023023988号-3
违法及侵权请联系:TEL:199 1889 7713 E-MAIL:2724546146@qq.com
本站由北京市万商天勤律师事务所王兴未律师提供法律服务