tianyicui / pack Goto Github PK

View Code? Open in Web Editor NEW

2.4K 82.0 366.0 1.91 MB

背包问题九讲

pack's People

Contributors

Stargazers

Watchers

Forkers

shanyuxiang yoyojade funtion sailspark rembau tanaaa84 ldfaiztt jianfengyao huoyao shaonian111111 zhoupeng39110 rexdf myzhk championl zhangjiandev renyapeng rainlee unix8net tentativity luonaibin chen0yang changdonglei gyang shiyuluo nanwan03 maxmengt tombeer2011 provemyself donghaoye ck2010 joey4s6l halloworld-yip xiaowanzi1 kathyrine exlsunshine godcowc pengweijian benedictking uranusz tianhongbo dsheng smilingcodes duihuhu steven1677 hrh007 amoursec jih488 sherlocksun0125 railsgem ii0 podongfeng huagsan swearos liuxiaozeeee robinloxley1 xinzhg archervanderwaal jiatoo forrestsu giserfly liuchsh01 universityofpennsylvania aa10000 wuzhigang05 zangshayang1 miniminiwhite liaopan jojo0099 fmxdd log4me muryliang xrenaissance deepwzh dhuleitao daixiaogang timegesake chenyncv jr-jy hawxchen hanth12 fashgek jason88888 kjkslove tianxpx lixiaosi33 janostudio freedom000 sonpakc resolvewang iurnah rubitree jinqgao kanghaibo jxlin jayvae huangzsdy bineanfrank huangsenlin123 wybeverglowxkx zcc888

pack's Issues

p06分组背包的一个问题

“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
这一句话能详细解释下为什么么？

章节 1.2 基本思路有 Bug

按文章所讲，写出的代码为

for (int i = 1; i <= N; i++) {
    for (int j = w[i - 1]; j <= W; j++) {
        F[i][j] = Math.max(F[i - 1][j - w[i - 1]] + v[i - 1], F[i - 1][j]);
    }
}

输出：

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	
0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	220

而正确代码应该为

for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= W; j++) {
        if (w[i - 1] <= j) {
            F[i][j] = Math.max(F[i - 1][j - w[i - 1]] + v[i - 1], F[i - 1][j]);
        } else {
            F[i][j] = F[i - 1][j];
        }
    }
}

输出：

0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	0	
0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	60	
0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	160	
0	0	0	0	0	0	0	0	0	0	60	60	60	60	60	60	60	60	60	60	100	100	100	100	100	100	100	100	100	100	160	160	160	160	160	160	160	160	160	160	180	180	180	180	180	180	180	180	180	180	220

动态规划的思考艺术

看到文中说从属于《动态规划的思考艺术》，请问动态规划的思考艺术在哪？

“1.2 基本思路”中没有考虑V<C_i的情况

“1.2 基本思路”中，伪代码内层循环用的是

for v ← C_i to V

因为这里还没有提到优化空间复杂度，用的是二维数组，所以当 V<C_i 时，要把 F [i − 1, v] 复制到 F [i, v]。

关于p.16最优方案的总数

beta1.2版16页，9.4最优方案的总数，伪代码是不是有点问题呢？

背包问题有没有 V3版本

第8讲第9 讲太简单了大佬有空补充下呗

I have just found the new version of knapsack problems.

https://www.kancloud.cn/kancloud/pack/70125

1.5一个常数优化

对内层V的优化应该是max(V-sigma(C_i), C_i) 而不是max(V-sigma(W_i), C_i)吧，
因为V是背包的容量，C_i是第i件物品消耗的容量

tianyicui / pack Goto Github PK

pack's People

Contributors

Stargazers

Watchers

Forkers

pack's Issues

p06分组背包的一个问题

章节 1.2 基本思路有 Bug

动态规划的思考艺术

“1.2 基本思路”中没有考虑V<C_i的情况

关于p.16最优方案的总数

背包问题有没有 V3版本

I have just found the new version of knapsack problems.

1.5一个常数优化

Recommend Projects

React

Vue.js

Typescript

TensorFlow

Django

Laravel

D3

Recommend Topics

javascript

web

server

Machine learning

Visualization

Game

Recommend Org

Facebook

Microsoft

Google

Alibaba

D3

Tencent