背包常规解法:
物品
0__1 __2 __3 __4 __5 __.. __ __ __ __ __ __ __ __
|__ __装
|__ __不装
dfs( int[] prices, int [] weights, int curW, int curP, int idx, int &maxN) {
//不装
dfs(prices, weights, curW, curP, idx+1, maxN)
//装
maxN = max( curP+ prices[idx] )
dfs(prices, weights, curW+weights[idx], curP+prices[idx], idx+1, maxN)
}
能处理 2^idx < MAXINT 的情况
dp(int[] prices, int [] weights, int &maxP[ int maxW ] ){
m......
阅读全文