제출 #851988

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
851988		Jere	Knapsack (NOI18_knapsack)	C++17	12 / 100	1 ms	348 KiB

knapsack

#include <bits/stdc++.h>
#define ll long long
using namespace std;

struct Item{
	int profit, weight, copy;
	Item() { 					
        profit = 0;
        weight = 0;
        copy = 0;
    }
	Item(int profit, int weight, int copy){
		this->profit=profit;
		this->weight=weight;
		this->copy=copy;
	}
};
static bool cmp(struct Item a, struct Item b){
	double r1=(double)a.profit/(double)a.weight;
	double r2=(double)b.profit/(double)b.weight;
	return r1>r2;
};
int knap(int W, struct Item arr[], int N){
	sort(arr, arr+N, cmp);
	int finalValue=0;
	for(int i=0; i<N; i++){
		while(arr[i].weight<=W&&arr[i].copy>0){
				W-=arr[i].weight;
				finalValue+=arr[i].profit;
				arr[i].copy--;
			}
	}
	return finalValue;
};

int main(){
	int w,n;
	cin>>w>>n;
	Item arr[n];
	for (int i=0; i<n; i++){
		cin>>arr[i].profit>>arr[i].weight>>arr[i].copy;//input array arr dgn struct item
	}
	cout<<knap(w, arr, n);
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 17
• Subtask 3: 0 / 20
• Subtask 4: 0 / 24
• Subtask 5: 0 / 27