HDU3466(가방 선착순)
Problem Description
Recently, iSea went to an ancient country. For such a long time, it was the most wealthy and powerful kingdom in the world. As a result, the people in this country are still very proud even if their nation hasn’t been so wealthy any more.
The merchants were the most typical, each of them only sold exactly one item, the price was Pi, but they would refuse to make a trade with you if your money were less than Qi, and iSea evaluated every item a value Vi.
If he had M units of money, what’s the maximum value iSea could get?
Input
There are several test cases in the input.
Each test case begin with two integers N, M (1 ≤ N ≤ 500, 1 ≤ M ≤ 5000), indicating the items’ number and the initial money.
Then N lines follow, each line contains three numbers Pi, Qi and Vi (1 ≤ Pi ≤ Qi ≤ 100, 1 ≤ Vi ≤ 1000), their meaning is in the description.
The input terminates by end of file marker.
Output
For each test case, output one integer, indicating maximum value iSea could get.
Sample Input
2 10 10 15 10 5 10 5 3 10 5 10 5 3 5 6 2 7 3
Sample Output
5 11
这道题和01背包很类似，唯一不同的就是买每件物品时多了一个限制条件，p，Q，v，需要钱数大于Q才能买，所以买东西需要有先后顺序。以前的01背包不用排序，dp[j] = max(dp[j],dp[j-w[i]]+v[i])表达的是这第i个物品要不要买，但同时也在判断第i个物品要不要先买，如果先买剩下的空间随便放，看是否得到的价值会更大。
A物品 p1,q1,v1;
B物品 p2,q2,v2
若先买A，至少需要p1+q2 (p1 == q1情况下）若现买B，至少需要p2+q1;
若A q2-p2;即差值大的先买，所以先买的应排到后面
#include
#include
#include
using namespace std;
int dp[5010];
struct note
{
int p,Q,v;
int ca;
} a[510];
bool cmp(note A,note B)
{
return A.ca < B.ca;
}
int main()
{
int n,m,i,j;
while(~scanf("%d%d",&n,&m))
{
for(i = 0;i=a[i].Q;j--)
{
dp[j] = max(dp[j],dp[j-a[i].p]+a[i].v);
}
printf("%d
",dp[m]);
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Rails Turbolinks를 페이지 단위로 비활성화하는 방법원래 Turobolinks란? Turbolinks는 링크를 생성하는 요소인 a 요소의 클릭을 후크로 하고, 이동한 페이지를 Ajax에서 가져옵니다. 그 후, 취득 페이지의 데이터가 천이 전의 페이지와 동일한 것이 있...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
