Notice
Recent Posts
문제 풀이 및 개발 공간
[과제 본문
import java.io.*;
import java.util.*;
public class Main{
static int[] p; static int[] w;
static int maxprofit; static int W; static int numbest; static int n;
static int[] include; static int[] bestset;
static int howK=0;
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
//입력값 받기
System.out.print("입력할 개수를 넣어주세요: ");
n=Integer.valueOf(br.readLine());
//배열생성 전역변수 초기화
numbest=0;
maxprofit=0;
p=new int[n+1]; w=new int[n+1]; include=new int[n+1]; bestset=new int[n+1];
System.out.print("공백을 기준으로 각각의 이익과 무게를 profit weight를 입력하세요: ");
String input=br.readLine();
st=new StringTokenizer(input);
//무게와 이익 값 저장
for(int i=1; i<=n; i++){
p[i]=Integer.valueOf(st.nextToken());
w[i]=Integer.valueOf(st.nextToken());
}
//제한무게 설정
System.out.print("제한 무게를 설정해주세요: ");
W=Integer.valueOf(br.readLine());
double before=System.nanoTime();
//백트래킹 돌리기
knapsack(0,0,0);
double after=System.nanoTime();
System.out.println("--백트래킹 알고리즘--");
//출력부분
bw.write(maxprofit+"\n");
bw.write("최대 이익이 되는 세트 조합: ");
for(int i=1; i<bestset.length; i++ ){
if(bestset[i]==1){
bw.write(i+" ");
}
}
bw.write("\nKnapack의 호출 수: "+howK+"\n");
bw.write("실생시간 단위(ns): "+(after-before));
bw.flush();
}
public static void knapsack(int i, int profit, int weight){
howK++;
if(weight <=W && profit>maxprofit){
maxprofit=profit;
numbest=i;
bestset=Arrays.copyOfRange(include, 0, n+1);
}
if(promising(i,profit,weight)){
include[i+1]=1;
knapsack(i+1, profit+p[i+1], weight+w[i+1]);
include[i+1]=0;
knapsack(i+1, profit, weight);
}
}
public static boolean promising(int i, int profit, int weight){
int j=0;
int k=0;
int totweight=0;
double bound=0.0;
if(weight>=W){
return false;
}
else{
j=i+1;
bound=profit;
totweight=weight;
while(j<=n && totweight+w[j]<=W){
totweight=totweight+w[j];
bound=bound+p[j];
j++;
}
}
k=j;
if(k<=n){
bound= bound+(W-totweight)*(double)p[k]/(double)w[k];
}
return bound>maxprofit;
}
}import java.io.*;
import java.util.*;
class P{
int v;
int w;
public P(int v, int w){
this.v=v;
this.w=w;
}
}
public class reverse {
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
PriorityQueue<P> que=new PriorityQueue<>(new Comparator<P>(){
public int compare(P o1, P o2){
return -(o1.v/o1.w-o2.v/o2.w);
}
});
StringBuilder sb=new StringBuilder();
for(int i=0; i<16; i++){
StringTokenizer st=new StringTokenizer(br.readLine());
int w=Integer.valueOf(st.nextToken());
int v=Integer.valueOf(st.nextToken());
que.offer(new P(v,w));
}
while(!que.isEmpty()){
P temp=que.poll();
sb.append(temp.v+" "+temp.w+" ");
}
bw.write(sb.toString());
bw.flush();
}
}import java.io.*;
import java.util.*;
class Point{
int level;
int profit;
int weight;
double bound;
int[] include;
public Point(int level, int profit, int weight, double bound, int[] include){
this.level=level;
this.profit=profit;
this.weight=weight;
this.bound=bound;
this.include=include;
}
}
public class Main2{
static int[] p; static int[] w;
static int maxprofit; static int W; static int numbest; static int n;
static int[] include; static int[] bestset;
static int howK=0; static int howP=0;
public static void main(String[] args) throws IOException{
BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;
//입력값 받기
System.out.print("입력할 개수를 넣어주세요: ");
n=Integer.valueOf(br.readLine());
//배열생성 전역변수 초기화
numbest=0;
maxprofit=0;
p=new int[n+1]; w=new int[n+1];
include=new int[n+1]; bestset=new int[n+1];
System.out.print("공백을 기준으로 각각의 이익과 무게를 profit weight를 입력하세요: ");
String input=br.readLine();
st=new StringTokenizer(input);
//무게와 이익 값 저장
for(int i=1; i<=n; i++){
p[i]=Integer.valueOf(st.nextToken());
w[i]=Integer.valueOf(st.nextToken());
}
//제한무게 설정
System.out.print("제한 무게를 설정해주세요: ");
W=Integer.valueOf(br.readLine());
//알고리즘 돌리기
//바운드가 큰게 먼저 나오도록 정렬 재설정
PriorityQueue<Point> que=new PriorityQueue<>(new Comparator<Point>(){
public int compare(Point o1, Point o2){
return -(int)((o1.bound-o2.bound)*100);
}
});
Point u=new Point(0,0,0,0,new int[n+1]);
Point v=new Point(0,0,0, 0,new int[n+1]);
v.bound=bound(v);
maxprofit=0;
que.offer(v);
double before=System.nanoTime();
while(!que.isEmpty()){
howK++;
Point temp=que.poll();
if(temp.bound>maxprofit){
u.include=Arrays.copyOfRange(temp.include,0,n+1);
u.level=temp.level+1;
u.weight=temp.weight+w[u.level];
u.profit=temp.profit+p[u.level];
u.include[u.level]=1;
if(u.weight<=W && u.profit>maxprofit){
maxprofit=u.profit;
bestset=Arrays.copyOfRange(u.include, 0,n+1);
}
u.bound=bound(u);
if(u.bound>maxprofit){
que.offer(new Point(u.level, u.profit , u.weight, u.bound, u.include));
}
else{
howK++;
}
u.weight=temp.weight;
u.profit=temp.profit;
u.bound=bound(u);
if(u.bound>maxprofit){
que.offer(new Point(u.level, u.profit, u.weight, u.bound, temp.include));
}
else{
howK++;
}
}
}
double after=System.nanoTime();
System.out.println("--Branch-and-Bound--");
//출력부분
bw.write(maxprofit+"\n");
bw.write("최대 이익이 되는 세트 조합: ");
for(int i=1; i<bestset.length; i++ ){
if(bestset[i]==1){
bw.write(i+" ");
}
}
bw.write("\nwhile 내부의 호출 수: "+howK+"\n");
bw.write("실생시간 단위(ns): "+(after-before));
bw.flush();
}
public static double bound(Point a){
howP++;
int j=0;
int k=0;
int totweight=0;
double bound=0.0;
if(a.weight>=W){
return 0;
}
else{
j=a.level+1;
bound=a.profit;
totweight=a.weight;
while(j<=n && totweight+w[j]<=W){
totweight=totweight+w[j];
bound=bound+p[j];
j++;
}
}
k=j;
if(k<=n){
bound= bound+(W-totweight)*(double)p[k]/(double)w[k];
}
return bound;
}
}