tianyicui / pack Goto Github PK
View Code? Open in Web Editor NEW背包问题九讲
背包问题九讲
“1.2 基本思路”中,伪代码内层循环用的是
for v ← C_i to V
因为这里还没有提到优化空间复杂度,用的是二维数组,所以当 V<C_i 时,要把 F [i − 1, v] 复制到 F [i, v]。
beta1.2版16页,9.4最优方案的总数,伪代码是不是有点问题呢?
按文章所讲,写出的代码为
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
看到文中说从属于《动态规划的思考艺术》,请问动态规划的思考艺术在哪?
“for v=V..0”这一层循环必须在“for 所有的i属于组k”之外。这样才能保证每一组内的物品最多只有一个会被添加到背包中。
这一句话能详细解释下为什么么?
第8讲 第9 讲 太简单了 大佬有空补充下呗
对内层V的优化应该是max(V-sigma(C_i), C_i) 而不是max(V-sigma(W_i), C_i)吧,
因为V是背包的容量,C_i是第i件物品消耗的容量
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.