use proconio::{fastout, input}; #[fastout] fn main() { input! { n: usize, w: usize, value: [u32; n], weight: [u32; n], } println!( "{}", output(solve( n, w, value.into_iter().zip(weight).collect::>() )) ); } fn solve(n: usize, w: usize, items: Vec<(u32, u32)>) -> Vec { let mut dp = vec![[0; 3001]; 3001]; for (i, (value, weight)) in items.iter().enumerate().rev() { for j in 0..*weight as usize { dp[i][j] = dp[i + 1][j]; } for j in (*weight as usize)..=w { dp[i][j] = dp[i + 1][j].max(dp[i + 1][j - *weight as usize] + value); } } let dp = dp; let mut ans = Vec::with_capacity(n); let mut rest_weight = w; for (i, (_, weight)) in items.into_iter().enumerate() { if dp[i][rest_weight] != dp[i + 1][rest_weight] { ans.push((i + 1) as u32); rest_weight -= weight as usize; } } ans } fn output(ans: Vec) -> String { ans.len().to_string() + "\n" + &ans .into_iter() .map(|x| x.to_string()) .collect::>() .join(" ") }