Skip to content

Instantly share code, notes, and snippets.

@Kroisse

Kroisse/ks.rs

Last active August 29, 2015 13:57
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Kroisse/9420018 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Kroisse/9420018 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
ks.rs
// #[feature(globs)];
extern crate collections;
// use std::iter::*;
use std::from_str::from_str;
// use std::str::from_utf8;
// use collections::hashmap::HashSet;
#[deriving(Clone)]
struct Knapsack {
score: uint,
desire : uint,
capacity: int,
item: ~[~[uint]]
}
struct KnapsackBranch<'a> { // record the stat
knap : Knapsack,
items: std::vec::Items<'a, ~[uint]>,
rec : ~uint,
current_max_score : Knapsack, // if origin max_score is changed, this branch will reviewed
// max_score : &'a mut Knapsack // global max score
}
impl Knapsack {
fn pick_item(&mut self, item: ~[uint]) {
self.capacity -= item[1] as int;
self.score += item[0];
self.item.push(item);
}
fn drop_item(&mut self, item_id: uint) {
for x in std::iter::range_step(self.item.len(), 0, -1) {
// let mut x : uint = self.item.len();
// loop {
// x -= 1;
if item_id == self.item[x][2] {
match self.item.remove(x) {
Some(item) => {
self.score -= item[0];
self.desire -= item[0];
self.capacity += item[1] as int;
}
None => ()
}
return;
}
}
return;
}
}
// #[deriving(Clone)]
// struct Item {
// value: uint,
// weight: uint,
// }
// impl <Knapsack> Iterator <Knapsack> for Knapsack {
// fn next(&mut self) -> Option<Knapsack> {
// }
// }
#[inline]
fn calc_knapsack_branch<'a>(max_score: &mut Knapsack, knapbr : ~KnapsackBranch<'a>, rec : uint, times : &mut uint) -> Option<~[KnapsackBranch<'a>]> {
calc_knapsack(knapbr.items,max_score, knapbr.knap, ~[], rec, times)
}
// TODO: should rewrite to spawn each branch
// it means, refactor that codes
// TODO: Hash Items, if Items is calculated, then continue
#[inline]
fn calc_knapsack<'a>(
items: std::vec::Items<'a, ~[uint]>, max_score: &mut Knapsack, knap : Knapsack, trash_knaps : ~[KnapsackBranch<'a>],
rec : uint, times : &mut uint) -> Option<~[KnapsackBranch<'a>]> {
// let mut rec : uint = rec;
let mut knap = knap;
let mut items = items;
let indent = "|".repeat(rec % 16);
debug!("{}search best combo...", indent)
let item = items.next();
debug!("{}next item is {:?}, times: {:?}", indent, item, times)
*times += 1;
match item {
Some(item) => {
if knap.desire >= max_score.desire {
if knap.score >= max_score.score {
if knap.capacity >= 0 {
*max_score = knap.clone();
debug!("{}found a current best combo: {:?}", indent, max_score);
} else {
debug!("{}it looks found a current best combo, but it is invaild. {:?}", indent, knap);
}
} else {
// debug!("{}it : {:?}", indent, knap.desire, max_score.desire);
}
} else {
debug!("{}current desire {:?} not bigger max_score {:?}, give up.", " ".repeat(rec), knap.desire, max_score.desire)
// I forgot something that is good optimize.
let knapbr: KnapsackBranch = KnapsackBranch {
knap : knap,
items: items,
rec : ~rec,
current_max_score : max_score.clone(),
// max_score: max_score
};
trash_knaps.push(knapbr);
return Some(trash_knaps)
}
if knap.capacity < item[1] as int {
debug!("{}next item is too large, give up. capacity: {} item_weight: {}", indent, knap.capacity, item[1])
debug!("{}knap: {:?}",indent ,knap)
if knap.score >= max_score.score { // if knap score bigger than max_score
// *max_score = knap.clone();
debug!("{}setting desire: {:?}\n{}setting desire desire: {:?} max_score: {:?}", indent, max_score,indent, knap.desire, max_score.desire);
max_score.desire = max_score.score;
}
return None
}
knap.pick_item(item.clone());
debug!("{}pick up a item {:?}, knap: {:?}", indent, item, knap)
// calc_knapsack(items,max_score, knap.clone(), trash_knaps, rec + 1, times);
// if !calc_knapsack(items,max_score, knap.clone(), rec + 1) {
knap.drop_item(item[2]);
// knap.item.pop();
debug!("{}drop a item {:?}, score: {:?}, desire: {:?}", indent, item, knap.score, knap.desire)
}
None => ()
}
return None
// }
// return true
// }
// }
// if knap.desire >= max_score.desire { // oh, I forgot somethings
// if knap.score >= max_score.score { // when this is last item, check it
// if knap.capacity >= 0 {
// *max_score = knap.clone();
// debug!("{}found a current best combo: {:?}", indent, max_score);
// // if max_score.desire < max_score.score { // I don't know does it will help. it seem always true.
// max_score.desire = max_score.score;
// // }
// debug!("{}setting desire: {:?}\n{}setting desire desire: {:?} max_score: {:?}", indent, max_score,indent, knap.desire, max_score.desire);
// } else if *times != 0 {
// debug!("{}it looks found a current best combo, but it is invaild. ", indent);
// }
// }
// }
// if score.len() > 0 {
// for x in score.iter() {
// score_now += x.score;
// }
// }
// let knapsack
}
// input file:
// first line meaning: `item counts, container capacity`
// other line meaning; `value
// 19 31181
// 1945 4990
// 321 1142
// 2945 7390
// 4136 10372
// 1107 3114
// 1022 2744
// 1101 3102
// 2890 7280
// 962 2624
// 1060 3020
// 805 2310
// 689 2078
// 1513 3926
// 3878 9656
// 13504 32708
// 1865 4830
// 667 2034
// 1833 4766
// 16553 40006
fn main() {
let mut stdin = std::io::stdio::stdin();
let x = {
let a : ~str =
match stdin.read_line() {
Ok(x) => {
info!("readline: {:?}", x);
x
},
Err(x) => fail!("when read line, occur unknown error. {}", x),
};
let a : ~[&str] = a.as_slice().split_terminator(' ').collect();
// let a = a.split(' ');
a
};
assert_eq!(x.len(), 2);
info!("readline: {:?}", x);
let items : uint = from_str(x[0]).unwrap_or(0);
info!("items: {} \t",items);
let capacity : int = from_str(x[1].trim()).unwrap_or(0);
info!("capacity: {}",capacity);
let mut item_list = {
let list = {
let mut l : ~[~str] = ~[];
for _ in range(0,items) {
let li = stdin.read_line().unwrap();
info!("{:?}", li);
l.push(li);
}
l
};
// let list = match from_utf8(list) {
// Some(x) => x.trim(),
// None => fail!("1cant turn bytes to utf8.")
// };
// info!("item_list: {:?}", a);
let list = list.iter().map( // lv1 vec
|line| {
// info!("line: {:?}", line);
let line : ~[uint] = line.split(' ').map(|z : &str| {
// info!("str to uint: {:?}", z);
from_str::<uint>(z.trim()).unwrap()
}).to_owned_vec();
assert_eq!(line.len(), 2);
// Item {
// value: line[0],
// weight: line[1],
// }
line.to_owned()
// }
// }
// result
}).to_owned_vec();
list
// let mut set = HashSet::new();
// for x in list {
// set.insert(x);
// }
// set
};
for x in range(0,item_list.len()) {
item_list[x].push(x)
}
// info!("item_list: {:?}", item_list);
item_list.sort_by(|a,b| *(&b[1].cmp(&a[1])));
info!("\nitem_list: {:?}", item_list);
// item_list.sort_by(|a,b| *(&a[0].cmp(&b[0])));
// info!("\nitem_list: {:?}", item_list);
let solve = {
let init = item_list.iter();
let desire = {
let mut max = 0;
for x in init.clone() {
max += x[0]
}
max
};
let mut max_score_knapsack = Knapsack {
score: 0,
desire : desire,
capacity: capacity,
item: ~[]
};
let knapsack = max_score_knapsack.clone();
let mut trash_knaps : ~[KnapsackBranch] = ~[];
// let mut score = 0;
// let mut max_scores_knap : Knapsack = ~[];
// let knap = knapsack.clone();
calc_knapsack(init, &mut max_score_knapsack, knapsack, trash_knaps, 0, &mut 0);
// let item = init.clone();
max_score_knapsack
};
info!("finally, solve is {:?}", solve)
let mut stderr = std::io::stdio::stdout();
let itemslot : ~str = {
let mut i : ~[~str] = ~[];
for _ in range(0, items) {
i.push(~"0 ")
}
for x in solve.item.iter() {
i[x[2]] = ~"1 "
}
let i = i.concat();
i.trim().to_owned()
};
stderr.write_str(format!("{} 0\n{}", solve.score, itemslot));
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment