sicily_1221(0-1 가방 문제)

제술: 작은 W가 게임을 발명했는데 그는 칠판에 숫자 a1, a2를 한 줄 썼다.an, 그리고 m라운드의 기회를 줍니다. 라운드마다 한 개의 수를 선택하여 지울 수 있습니다. 이어서 남은 숫자마다ai는 한 개의 값을 줄여야 합니다.이렇게 m라운드를 반복하면 네가 지운 모든 숫자의 합이 네가 얻은 점수다.이 점수를 최대화하라고.입력: 첫 번째 줄, 숫자의 개수를 나타내는 정수 n(1<=n<=200).두 번째 줄은 라운드 수를 나타내는 정수 m(1<=m<=n)이다.다음 줄에는 n개가 10000을 넘지 않는 정수, a1, a2...an이 있는데 원시 숫자의 마지막 줄에는 n개가 500을 넘지 않는 정수, b1, b2...bn, 라운드당 숫자의 체감을 나타내는 값 출력: 최대 득점
제목 분석: 사실 0-1 가방 문제입니다. 가방의 크기는 m이고 n개의 아이템이 있습니다. 아이템은 가방의 1 단위 공간을 소모하여 가방에 넣을 수 있는 물건의 최대치를 구합니다.만약 단지 이렇다면 이 문제는 누드의 가장 기본적인 가방 문제다. 그러나 물품은 잡는 순서에 따라 가치가 감소하고 천천히 들수록 물품의 가치가 작아진다. 그러면 문제는 어떻게 총가치를 가장 크게 할 수 있느냐는 것이다.사고방식 분석: 본래 이것은 동태적인 기획의 문제였지만 제목의 가치가 감소하는 조건 때문에 욕심스러운 제목이 된 것 같다.그렇다면 우리는 어떻게 이 최대치를 확정해야 합니까?만약 우리가 확정된 m개수(n==m)를 취한다면 우리는 당연히 먼저 b대수를 취해야만 총액을 최대화할 수 있다.만약 mfor(int i=0;i<n;i++) for(int j=m;j>0;j--) dp[j]=max(dp[j],dp[j-1]+num[i].a-num[i].b*(j-1));
그러나bi가 다르면 상기 코드가 틀릴 수 있다. 예를 들어 다음과 같다. 입력: 3, 2, 8, 8, 6, 1, 2, 3. 바로 위의 코드로 튀어나온 것은:14이다. 그러나 가장 큰 값은 두 번째를 먼저 취하고 첫 번째를 취하는 것이다. 마지막 결과:15는 어디에 틀렸을까?우리는 두 번째 물품을 순환할 때(상기 코드의 순환은 첫 번째는 n개의 물품에 근거하고 두 번째는 가방의 공간에 근거한다)를 고려하여 dp[i]와 dp[i-1]+물품 i를 비교해야 한다. 이때 dp[1]은 8이고 dp[2]는 7이기 때문에 dp[2-1]+num[1]이다.a-num[1].b*(2-1)는 8+6(8-2)=14로 변한다. 즉, 확실한 두 개의 물건을 알면서도 먼저 뽑은 비작은 것은 우리가 앞에서 말한 욕심의 규칙을 현저히 위반한다.그러므로 우리의 총 가치가 물건 얻는 순서의 영향을 받지 않도록 하기 위해서 우리는 규칙을 적용하고 b대부터 시작해야 한다. 그래서 문제를 해결해야 한다!코드가 나왔어요.

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

int n,m,dp[205];

struct node{
    int a,b;
}num[205];

bool cmp(node x,node y){
    return x.b>y.b;
}

int main()
{
    scanf("%d %d",&n,&m);
    for(int i=0;i<n;i++)
        scanf("%d",&num[i].a);
    for(int i=0;i<n;i++)
        scanf("%d",&num[i].b);

    sort(num,num+n,cmp);

    for(int i=0;i<n;i++)
    {
        for(int j=m;j>0;j--)
        {
            dp[j]=max(dp[j],dp[j-1]+num[i].a-num[i].b*(j-1));
        }
    }
    printf("%d
",dp[m]);

    return 0;
}

총괄: 욕심 많은 동태 계획을 추가한 절대적인 좋은 문제!