6
HDU3466 Proud Merchants（01背包）
source link: https://arminli.com/hdu3466/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
HDU3466 Proud Merchants（01背包）
March 10, 2016
01 背包问题，附加条件是每次购买必须拥有超过 q 的钱数。
将 q-p 从小大到排序后直接按照背包搞。
关于 q-p 从小到大排序的原因，我是这么想的：假设 q-p 无穷小，那么就变成了一个裸的 01 背包问题，肯定要先处理小的以免影响后面运算。网上看到一个人的想法也不错：假设两个物品 A：p1，q1 和 B：p2，q2，先买 A 的话则需要 p1+q2 的钱，先买 B 的话需要 p2+q1 的钱，若 p1+q2>p2+q1 则 q1-p1 小于 q2-p2.
#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include <vector>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[5005];
struct node{
int p, q, v;
}a[1005];
int cmp(node x,node y){
return x.q-x.p < y.q-y.p;
}
int main(){
//freopen("a.txt", "r", stdin);
int n, m;
while(scanf("%d %d", &n, &m) != EOF){
memset(dp, 0, sizeof(dp));
for(int i = 1; i <= n; i++)
scanf("%d %d %d", &a[i].p, &a[i].q, &a[i].v);
sort(a+1, a+1+n, cmp);
for(int i = 1; i <= n; i++){
for(int j = m; j >= a[i].q; j--){
dp[j] = max(dp[j], dp[j-a[i].p]+a[i].v);
}
}
cout << dp[m] << endl;
}
return 0;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK