|
Time Limit: 1000MS |
Memory Limit: 10000K |
|
|
Total Submissions: 24132 |
Accepted: 8446 |
Description
N=3, n1=10, D1=100, n2=4, D2=50, n3=5, D3=10
means the machine has a supply of 10 bills of @100 each, 4 bills of @50 each, and 5 bills of @10 each.
Call cash the requested amount of cash the machine should deliver and write a program that computes the maximum amount of cash less than or equal to cash that can be effectively delivered according to the available bill supply of the machine.
Notes:
@ is the symbol of the currency delivered by the machine. For instance, @ may stand for dollar, euro, pound etc.
Input
cash N n1 D1 n2 D2 ... nN DN
where 0 <= cash <= 100000 is the amount of cash requested, 0 <=N <= 10 is the number of bill denominations and 0 <= nk <= 1000 is the number of available bills for the Dk denomination, 1 <= Dk <= 1000, k=1,N. White spaces can occur freely between the numbers in the input. The input data are correct.
Output
Sample Input
735 3 4 125 6 5 3 350
633 4 500 30 6 100 1 5 0 1
735 0
0 3 10 100 10 50 10 10
Sample Output
735
630
0
0
题意， 给你最大的钱数 Case ，和 nk 种不同的面值, 每种面值D1...DN 对应的数量 n1....nN, 找出不超过最大钱数Case
思路：多重背包
import java.io.*;
import java.util.*;
/*
*
* author : deng_hui_long
* Date : 2013-8-31
*
*/
public class Main {
int Case,n;
int dp[]=new int[1000000];
public static void main(String[] args) {
new Main().work();
}
void work(){
Scanner sc=new Scanner(new BufferedInputStream(System.in));
while(sc.hasNext()){
Case=sc.nextInt();
n=sc.nextInt();
if(n==0&&Case==0)
break;
Node node[]=new Node[n];
Arrays.fill(dp,0);
for(int i=0;i<n;i++){
int a=sc.nextInt();
int b=sc.nextInt();
node[i]=new Node(a,b);
}
for(int i=0;i<n;i++){
multiplePack(node[i].val,node[i].val,node[i].cost);
}
System.out.println(dp[Case]);
}
}
//多重背包
void multiplePack(int cost,int weight,int amount){
if(cost*amount>=Case)//超过最大的钱数，按完全背包处理
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);
}
}
//完全背包
void completePack(int cost,int weight){
for(int i=cost;i<=Case;i++){
dp[i]=Math.max(dp[i],dp[i-cost]+weight);
}
}
//01背包
void zeroOnePack(int cost,int weight){
for(int i=Case;i>=cost;i--)
dp[i]=Math.max(dp[i],dp[i-cost]+weight);
}
class Node{
int cost;
int val;
Node(int cost,int val){
this.cost=cost;
this.val=val;
}
}
}