HDU 1171 Big Event in HDU(マルチバックパック)
3641 ワード
Big Event in HDU
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 19108 Accepted Submission(s): 6707
Problem Description
Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0
Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0A test case starting with a negative integer terminates input and this test case is not to be processed.
Output
For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.
Sample Input
2 10 1 20 1 3 10 1 20 2 30 1 -1
Sample Output
20 10 40 40
题意:学校はコンピュータ学院とソフトウェア学院に分けて、N种类の価値の设备が既知で、それぞれの価値はvで、m件があって、今设备を2つの学院の中に分けて、すべての部分の価値をできるだけ等しくします(もし等しくないならば第1部分を第2部分より大きくします).
多重バックパック:
考え方:リュックサックの体積は総価値の半分で、それから多重リュックサックで最大値を求めます.
01リュック、完全リュック、多重リュック、テンプレートコード:http://blog.csdn.net/deng_hui_long/article/details/10603015
Time Limit: 10000/5000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 19108 Accepted Submission(s): 6707
Problem Description
Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don't know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0
Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 -- the total number of different facilities). The next N lines contain an integer V (0
Output
For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.
Sample Input
2 10 1 20 1 3 10 1 20 2 30 1 -1
Sample Output
20 10 40 40
题意:学校はコンピュータ学院とソフトウェア学院に分けて、N种类の価値の设备が既知で、それぞれの価値はvで、m件があって、今设备を2つの学院の中に分けて、すべての部分の価値をできるだけ等しくします(もし等しくないならば第1部分を第2部分より大きくします).
多重バックパック:
考え方:リュックサックの体積は総価値の半分で、それから多重リュックサックで最大値を求めます.
01リュック、完全リュック、多重リュック、テンプレートコード:http://blog.csdn.net/deng_hui_long/article/details/10603015
import java.io.*;
import java.util.*;
public class Main {
int n;
int dp[]=new int[100000];
int sum,vsum;
public static void main(String[] args) {
new Main().work();
}
void work(){
Scanner sc=new Scanner(new BufferedInputStream(System.in));
while(sc.hasNext()){
n=sc.nextInt();
if(n<0) break;
Node node[]=new Node[n];
Arrays.fill(dp, 0);
vsum=sum=0;
for(int i=0;i<n;i++){
int v=sc.nextInt();
int m=sc.nextInt();
sum+=v*m;
node[i]=new Node(v,m);
}
vsum=sum>>1;// ， 2： ： 2
for(int i=0;i<n;i++){
multiplyPack(node[i].v,node[i].v,node[i].m);
}
System.out.println((sum-dp[vsum])+" "+dp[vsum]);
}
}
void multiplyPack(int cost,int weight,int amount){
if(cost*amount>=vsum){// ， ,
completePack(cost,weight);
}
else{// ， 01
int k=1;
while(k<amount){
zeroOnePack(k*cost,k*weight);
amount-=k;
k<<=1;// 2
}
zeroOnePack(amount*cost,amount*weight);
}
}
//01
void zeroOnePack(int cost,int weight){
for(int i=vsum;i>=cost;i--){
dp[i]=Math.max(dp[i],dp[i-cost]+weight);
}
}
//
void completePack(int cost,int weight){
for(int i=cost;i<=vsum;i++){
dp[i]=Math.max(dp[i],dp[i-cost]+weight);
}
}
class Node{
int v;
int m;
Node(int v,int m){
this.v=v;
this.m=m;
}
}
}