题目:http://acm.hdu.edu.cn/showproblem.php?pid=2546
import java.util.Scanner;
public class Main {
public int max(int a,int b){
return a>b?a:b;
}
public int packet(int n,int price[],int money,int exp){
int f[]=new int[1024];
for(int i=0;i<n;i++){
f[0]=0;
}
for(int i=0;i<n;i++)
if(i!=exp) //最贵的菜留到最后买
for(int j=money;j>=price[i];j--){
f[j]=max(f[j],f[j-price[i]]+price[i]);
}
return money-f[money];
}
public static void main(String[] args) {
Main m=new Main();
Scanner sc=new Scanner(System.in);
int n; //菜的数量
int money; //余额
int price[]=new int[1024]; //菜的价格
while(sc.hasNext()){
int max=0; //记录最贵的菜
int exp=0; //记录最贵的菜的下标
n=sc.nextInt();
if(n==0)
break;
for(int i=0;i<n;i++){
price[i]=sc.nextInt();
if(max<price[i]){
max=price[i];
exp=i;
}
}
money=sc.nextInt();
if(money>=5){
System.out.println(m.packet(n,price,money-5,exp)+5-max); //买最贵的菜后的余额
}
else{
System.out.println(money);
}
}
}
}
分享到:
相关推荐
hdu-acm源代码(上百题)hdu-acm源代码、hdu-acm源代码hdu-acm源代码
算法-数塔(HDU-2084).rar
算术(HDU-6715).rar
最短路(HDU-2544).rar
算法-确定比赛名次(HDU-1285).rar
算法-连连看(HDU-1175)(包含源程序).rar
算法-命运(HDU-2571)(包含源程序).rar
算法-欧拉回路(HDU-1878)(包含源程序).rar
算法-迷宫城堡(HDU-1269)(包含源程序).rar
算法-免费馅饼(HDU-1176)(包含源程序).rar
算法-排列2(HDU-1716)(包含源程序).rar
算法-六度分离(HDU-1869)(包含源程序).rar