首页 > 其他 > 详细

G面经prepare: BuyGoods

时间:2016-01-17 06:29:14      阅读:99      评论:0      收藏:0      [点我收藏+]
给你一部分钱和一些不同价钱的商品,如何在最多买K件商品的情况下尽可能多的花掉手里的钱。
举例:口袋里的钱数: 10;   K=2     产品价格: [3, 6, 8, 7, 9]   输出 3, 7

Backtracking:

 1 package BuyGoods;
 2 import java.util.*;
 3 
 4 public class Solution {
 5     static int minRemain = 0;
 6 
 7     public ArrayList<Integer> optimize(int money, int[] prices, int k) {
 8         9         ArrayList<Integer> result = new ArrayList<Integer>();
10         ArrayList<Integer> path = new ArrayList<Integer>();
11         minRemain = money;
12         helper(result, path, money, prices, 0, k);
13         return result;
14     }
15     
16     public void helper(ArrayList<Integer> result, ArrayList<Integer> path, int remain, int[] prices, int pos, int times) {
17         if (remain < 0 || times<0) return;
18         if (remain < minRemain) {
19             minRemain = remain;
20             result.clear();
21             result.addAll(path);
22         }
23         for (int i=pos; i<prices.length; i++) {
24             path.add(prices[i]);
25             helper(result, path, remain-prices[i], prices, i+1, times-1);
26             path.remove(path.size()-1);
27         }
28         
29     }
30 
31     /**
32      * @param args
33      */
34     public static void main(String[] args) {
35         // TODO Auto-generated method stub
36         Solution sol = new Solution();
37         ArrayList<Integer> result = sol.optimize(10, new int[]{7,8,1,6,9}, 3);
38         System.out.println(result);
39     }
40 
41 }

 

G面经prepare: BuyGoods

原文:http://www.cnblogs.com/EdwardLiu/p/5136746.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!