Simple Knapsack(AtCoder-2556)

3018 단어 #AtCoder동적 계획-가방 문제
Problem Description
You have N items and a bag of strength W. The i-th item has a weight of wi and a value of vi.
You will select some of the items and put them in the bag. Here, the total weight of the selected items needs to be at most W.
Your objective is to maximize the total value of the selected items.
Constraints
  • 1≤N≤100
  • 1≤W≤109
  • 1≤wi≤109
  • For each i=2,3,…,N, w1≤wi≤w1+3.
  • 1≤vi≤107
  • W, each wi and vi are integers.

    • Input
    Input is given from Standard Input in the following format:
    N W w1 v1 w2 v2 : wN vN
    Output
    Print the maximum possible total value of the selected items.
    Example
    Sample Input 1
    4 6 2 1 3 4 4 10 3 4
    Sample Output 1
    11 The first and third items should be selected.
    Sample Input 2
    5 400 3 1 4 1 5
    Sample Output 2
    13 The second and fourth items should be selected.
    Sample Input 3
    4 10 1 100 1 100 1 100 1 100
    Sample Output 3
    400 You can take everything.
    Sample Input 4
    4 1 10 100 10 100 10 100 10 100
    Sample Output 4
    0 You can take nothing.
    제목: n개 아이템, 가방 용량 w, i개 아이템 무게 와이, 가치vi, 최대 가치 추구
    가방
    용량 W는 최대 1E9로 배열 범위를 벗어나므로 최적화가 필요합니다.
    모든 물품의 무게는 [w1, w1+3] 범위 내에 있기 때문에 w1을 제시할 수 있다. 원래의 상태 dp[i][j]는 앞의 i개 물품의 무게가 j일 때의 최대 가치를 나타내고 w1을 제시한 후에 dp[i][j]를 dp[j][j][k]로 바꾸면 앞의 i개 물품이 k*w1+j의 품질을 차지할 때의 최대 가치를 나타낸다. 그 중에서 k는 k개 물품을 넣고 j는 더 많은 품질을 나타내며 w1을 제시했기 때문에많이 나오는 퀄리티 j는 300을 넘지 않아요.
    Source Program 
    #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define EPS 1e-9
#define PI acos(-1.0)
#define INF 0x3f3f3f3f
#define LL long long
const int MOD = 1E9+7;
const int N = 500+5;
const int dx[] = {-1,1,0,0,-1,-1,1,1};
const int dy[] = {0,0,-1,1,-1,1,-1,1};
using namespace std;
LL w[N],v[N];
LL dp[N][N][N];
int main(){
    LL n,W;
    scanf("%lld%lld",&n,&W);
    for(int i=1;i<=n;i++)
        scanf("%lld%lld",&w[i],&v[i]);

    LL w1=w[1];
    for(int i=1;i<=n;i++)
        w[i]-=w1;
    for(int i=1;i<=n;i++){
        for(int j=0;j<=n;j++){
            for(int k=1;k<=n;k++){
                if(j>=w[i]){
                    dp[i][j][k]=max(dp[i-1][j][k],dp[i-1][j-w[i]][k-1]+v[i]);
                }
                else{
                    dp[i][j][k]=dp[i-1][j][k];
                }
            }
        }
    }

    LL res=0;
    for(int j=0;j<=300;j++){
        for(int k=0;k<=n;k++){
            if(k*w1+j<=W){
                res=max(res,dp[n][j][k]);
            }
        }
    }
    printf("%lld
    ",res);

    return 0;
}

    Kdan Mobile Software Ltd.
    JS 조건 판단 if 문장

    좋은 웹페이지 즐겨찾기

    개발자 우수 사이트 수집

    개발자가 알아야 할 필수 사이트 100선 추천 우리는 당신을 위해 100개의 자주 사용하는 개발자 학습 사이트를 정리했습니다
    best100-homepage