Skip to content

Instantly share code, notes, and snippets.

@kazurof
Last active August 29, 2015 14:05
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save kazurof/4865fa5ab62c8aae09af to your computer and use it in GitHub Desktop.
Save kazurof/4865fa5ab62c8aae09af to your computer and use it in GitHub Desktop.
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Main {
/**
* 添字人数になるように会社を選んだ組み合わせの時の総コスト。
* {@link #NOT_ASSIGNED} の場合はそのような組み合わせは存在しない。
*/
static int[] costByNumOfMember;
/**
* {@link #costByNumOfMember} において、
* そのような人数に対する会社の組み合わせは存在しないことを表現する。
*/
static final int NOT_ASSIGNED = -1;
/** 全ての会社を選択した場合の人数 */
static int numOfMemberIfUseAll;
/** 必要な人数 */
static int requiedNumOfMember;
/** 会社の数 */
static int numOfCompany;
public static void main(String[] args) {
List<Company> companyList = new ArrayList<Company>();
// 入力データの読み込み。
try (Scanner scanner = new Scanner(System.in)) {
requiedNumOfMember = scanner.nextInt();
numOfCompany = scanner.nextInt();
for (int i = 0; i < numOfCompany; i++) {
Company company = new Company(scanner.nextInt(), scanner.nextInt());
companyList.add(company);
numOfMemberIfUseAll += company.members;
}
};
costByNumOfMember = new int[numOfMemberIfUseAll + 1];
for (int i = 0; i <= numOfMemberIfUseAll; i++) {
costByNumOfMember[i] = NOT_ASSIGNED;
}
// それぞれの会社毎に処理
for (Company company : companyList) {
for (int i = numOfMemberIfUseAll; company.members < i; i--) {
int costWithoutThisCompany = costByNumOfMember[i - company.members];
if (0 < costWithoutThisCompany) {
updateCostByNumOfMember(costWithoutThisCompany + company.cost, i);
}
}
// この会社のみを利用することを検討する必要がある場合
updateCostByNumOfMember(company.cost, company.members);
}
// 結果の検索と表示
int result = -1;
for (int i = requiedNumOfMember; i <= numOfMemberIfUseAll; i++) {
if (result < 0 ||
(costByNumOfMember[i] >= 0 && result > costByNumOfMember[i])) {
result = costByNumOfMember[i];
}
}
System.out.println(result);
}
static void updateCostByNumOfMember(int newCost, int members) {
if (costByNumOfMember[members] == NOT_ASSIGNED
|| newCost < costByNumOfMember[members]) {
costByNumOfMember[members] = newCost;
}
}
}
class Company {
Company(int members, int cost) {
this.members = members;
this.cost = cost;
}
int members;
int cost;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment