c*e
2 楼
In an exam you have n problems to work on. i=0, 1, ..., n-1.
The i-th problem takes you x[i] minutes, and give you a score s[i].
You have 60 minutes to work on them. How can you get the best score?
The i-th problem takes you x[i] minutes, and give you a score s[i].
You have 60 minutes to work on them. How can you get the best score?
T*i
3 楼
金正日的死因找到了：:2011-11-23：《张召忠：朝鲜半岛近期不会出现紧张局势》
c*e
4 楼
直接上片片吧，浪太大，小样都不敢靠近海啊~ 还是水狗呢~
周五用狗粮教shake,玩了不到5分钟，基本会抬手了。周六出去玩一天，懒妈没有力气
training了。周日早上遛回来，没有拿吃的，没有抱希望，说了一句shake,人家居然把
小爪子放在我的手心了！！！！！！！而且绝对可重复，也和它爹玩了一把，把两狗奴
给乐坏了！！！！！！！！！
今天晚上坐在书桌前，小B过来找我几次要睡毯子并在我脚边，我都没有理她（后妈忙
着倒照片）。小样估计自己跑到沙发那里睡毯子了。倒完照片我突然想起来，问一声，
小B呢？不到5秒钟，小家伙就把下巴搁在了我的腿上。感动得后妈马上把毯子搬到书桌
下，小样就一直靠着我的脚睡着:D
周五用狗粮教shake,玩了不到5分钟，基本会抬手了。周六出去玩一天，懒妈没有力气
training了。周日早上遛回来，没有拿吃的，没有抱希望，说了一句shake,人家居然把
小爪子放在我的手心了！！！！！！！而且绝对可重复，也和它爹玩了一把，把两狗奴
给乐坏了！！！！！！！！！
今天晚上坐在书桌前，小B过来找我几次要睡毯子并在我脚边，我都没有理她（后妈忙
着倒照片）。小样估计自己跑到沙发那里睡毯子了。倒完照片我突然想起来，问一声，
小B呢？不到5秒钟，小家伙就把下巴搁在了我的腿上。感动得后妈马上把毯子搬到书桌
下，小样就一直靠着我的脚睡着:D
h*2
5 楼
然后肚子大了一圈。
c*e
6 楼
Assumptions:
1. You do not get partial credit on a problem.
2. If you spend x[i] minutes on i-th problem, you will get the s[i] points.
1. You do not get partial credit on a problem.
2. If you spend x[i] minutes on i-th problem, you will get the s[i] points.
T*i
7 楼
【在 T****i 的大作中提到】
: 金正日的死因找到了：:2011-11-23：《张召忠：朝鲜半岛近期不会出现紧张局势》
o*l
8 楼
lol水狗不敢下水
【在 c*********e 的大作中提到】
: 直接上片片吧，浪太大，小样都不敢靠近海啊~ 还是水狗呢~
: 周五用狗粮教shake,玩了不到5分钟，基本会抬手了。周六出去玩一天，懒妈没有力气
: training了。周日早上遛回来，没有拿吃的，没有抱希望，说了一句shake,人家居然把
: 小爪子放在我的手心了！！！！！！！而且绝对可重复，也和它爹玩了一把，把两狗奴
: 给乐坏了！！！！！！！！！
: 今天晚上坐在书桌前，小B过来找我几次要睡毯子并在我脚边，我都没有理她（后妈忙
: 着倒照片）。小样估计自己跑到沙发那里睡毯子了。倒完照片我突然想起来，问一声，
: 小B呢？不到5秒钟，小家伙就把下巴搁在了我的腿上。感动得后妈马上把毯子搬到书桌
: 下，小样就一直靠着我的脚睡着:D
【在 c*********e 的大作中提到】
: 直接上片片吧，浪太大，小样都不敢靠近海啊~ 还是水狗呢~
: 周五用狗粮教shake,玩了不到5分钟，基本会抬手了。周六出去玩一天，懒妈没有力气
: training了。周日早上遛回来，没有拿吃的，没有抱希望，说了一句shake,人家居然把
: 小爪子放在我的手心了！！！！！！！而且绝对可重复，也和它爹玩了一把，把两狗奴
: 给乐坏了！！！！！！！！！
: 今天晚上坐在书桌前，小B过来找我几次要睡毯子并在我脚边，我都没有理她（后妈忙
: 着倒照片）。小样估计自己跑到沙发那里睡毯子了。倒完照片我突然想起来，问一声，
: 小B呢？不到5秒钟，小家伙就把下巴搁在了我的腿上。感动得后妈马上把毯子搬到书桌
: 下，小样就一直靠着我的脚睡着:D
p*2
9 楼
DP吧。
N*m
10 楼
太强大了！
【在 T****i 的大作中提到】
【在 T****i 的大作中提到】
c*e
11 楼
她太小只了，平静一点的海还是很喜欢的，那天的风大浪大，感觉海面比人高一截~
【在 o********l 的大作中提到】
: lol水狗不敢下水
【在 o********l 的大作中提到】
: lol水狗不敢下水
x*n
12 楼
Knapsack.
B*e
13 楼
那个神一样的女记者最近有没有到过朝鲜？
m*h
14 楼
可以跟破狗学习一下，呵呵
【在 c*********e 的大作中提到】
: 她太小只了，平静一点的海还是很喜欢的，那天的风大浪大，感觉海面比人高一截~
【在 c*********e 的大作中提到】
: 她太小只了，平静一点的海还是很喜欢的，那天的风大浪大，感觉海面比人高一截~
s*n
15 楼
0-1背包问题，DP解法看这个：
http://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%
http://zh.wikipedia.org/wiki/%E8%83%8C%E5%8C%85%E9%97%AE%E9%A2%
B*u
16 楼
张将军总在关键时刻象神一样出现
N*t
17 楼
太可爱了！吓得直跑～
她是什么size的poodle啊？
她是什么size的poodle啊？
D*g
18 楼
/**
* In an exam you have n problems to work on. i=0, 1, ..., n-1.
The i-th problem takes you x[i] minutes, and give you a score s[i].
You have 60 minutes to work on them. How can you get the best score?
*/
static class DPElement {
int value;
int prevCostIdx; // 0-based cost idx
int takenThisElement; // 0/1, indicating whether taking current
element, idx 0 based.
public DPElement() {
value = 0;
prevCostIdx = 0;
takenThisElement = 0;
}
}
static void knapSackProblemSolving(final int[] x, final int[] s, final
int t) {
if (x == null || s == null || x.length == 0 || s.length == 0 || x.
length != s.length || t <= 0) {
throw new IllegalArgumentException();
}
DPElement[][] dp = new DPElement[x.length + 1][t + 1];
for (int i = 0; i < dp.length; ++i) {
for (int j = 0; j < dp[0].length; ++j) {
dp[i][j] = new DPElement();
}
}
for (int i = 1; i <= x.length; ++i) {
for (int j = 1; j <= t; ++j) {
int val = j >= x[i-1] ? s[i - 1] + dp[i-1][j-x[i-1]].value :
0;
if (x[i-1] <= j && val > dp[i-1][j].value) {
dp[i][j].value = val;
dp[i][j].prevCostIdx = j - x[i-1];
dp[i][j].takenThisElement = 1;
} else {
dp[i][j].value = dp[i-1][j].value;
dp[i][j].prevCostIdx = j;
dp[i][j].takenThisElement = 0;
}
}
}
System.out.println("Best score is " + dp[x.length][t].value);
System.out.print("Taken elements: {");
int time = t;
for (int i = x.length; i > 0; --i) {
if (dp[i][time].takenThisElement == 1) {
System.out.print("");
}
time = dp[i][time].prevCostIdx;
}
System.out.println("}");
}
static void testKnapSackProblemSolving() {
int[] x = new int[] {59, 50, 10, 5, 2, 3, 58, 57, 1};
int[] s = new int[] {117, 99, 20, 10, 3, 5, 115, 114, 1};
knapSackProblemSolving(x, s, 60);
}
【在 x*********n 的大作中提到】
: Knapsack.
* In an exam you have n problems to work on. i=0, 1, ..., n-1.
The i-th problem takes you x[i] minutes, and give you a score s[i].
You have 60 minutes to work on them. How can you get the best score?
*/
static class DPElement {
int value;
int prevCostIdx; // 0-based cost idx
int takenThisElement; // 0/1, indicating whether taking current
element, idx 0 based.
public DPElement() {
value = 0;
prevCostIdx = 0;
takenThisElement = 0;
}
}
static void knapSackProblemSolving(final int[] x, final int[] s, final
int t) {
if (x == null || s == null || x.length == 0 || s.length == 0 || x.
length != s.length || t <= 0) {
throw new IllegalArgumentException();
}
DPElement[][] dp = new DPElement[x.length + 1][t + 1];
for (int i = 0; i < dp.length; ++i) {
for (int j = 0; j < dp[0].length; ++j) {
dp[i][j] = new DPElement();
}
}
for (int i = 1; i <= x.length; ++i) {
for (int j = 1; j <= t; ++j) {
int val = j >= x[i-1] ? s[i - 1] + dp[i-1][j-x[i-1]].value :
0;
if (x[i-1] <= j && val > dp[i-1][j].value) {
dp[i][j].value = val;
dp[i][j].prevCostIdx = j - x[i-1];
dp[i][j].takenThisElement = 1;
} else {
dp[i][j].value = dp[i-1][j].value;
dp[i][j].prevCostIdx = j;
dp[i][j].takenThisElement = 0;
}
}
}
System.out.println("Best score is " + dp[x.length][t].value);
System.out.print("Taken elements: {");
int time = t;
for (int i = x.length; i > 0; --i) {
if (dp[i][time].takenThisElement == 1) {
System.out.print("");
}
time = dp[i][time].prevCostIdx;
}
System.out.println("}");
}
static void testKnapSackProblemSolving() {
int[] x = new int[] {59, 50, 10, 5, 2, 3, 58, 57, 1};
int[] s = new int[] {117, 99, 20, 10, 3, 5, 115, 114, 1};
knapSackProblemSolving(x, s, 60);
}
【在 x*********n 的大作中提到】
: Knapsack.
H*7
19 楼
张将军孔教授双管齐下，金二实在是顶不住啊
c*e
20 楼
恩，我们要干爹的言传身教！
【在 m***h 的大作中提到】
: 可以跟破狗学习一下，呵呵
【在 m***h 的大作中提到】
: 可以跟破狗学习一下，呵呵
p*w
21 楼
说了好久了
【在 T****i 的大作中提到】
: 金正日的死因找到了：:2011-11-23：《张召忠：朝鲜半岛近期不会出现紧张局势》
【在 T****i 的大作中提到】
: 金正日的死因找到了：:2011-11-23：《张召忠：朝鲜半岛近期不会出现紧张局势》
c*e
22 楼
她爹看到照片上她跑的样子笑坏了，话说这张照片是在他们不知道的情况下拍的。
小B是miniature poodle, 10lbs以下才算toy,我们快13lbs了:P
【在 N******t 的大作中提到】
: 太可爱了！吓得直跑～
: 她是什么size的poodle啊？
小B是miniature poodle, 10lbs以下才算toy,我们快13lbs了:P
【在 N******t 的大作中提到】
: 太可爱了！吓得直跑～
: 她是什么size的poodle啊？
d*e
23 楼
其实是因为最近送的蜡像，金正日看到老妈张开双臂，知道中国同志的意思是让他早点
去见他妈去。
去见他妈去。
m*h
24 楼
好的
【在 c*********e 的大作中提到】
: 恩，我们要干爹的言传身教！
【在 c*********e 的大作中提到】
: 恩，我们要干爹的言传身教！
H*7
25 楼
这是我党的恶毒诅咒：金正日，你他妈的快成腊肉了。
【在 d***e 的大作中提到】
: 其实是因为最近送的蜡像，金正日看到老妈张开双臂，知道中国同志的意思是让他早点
: 去见他妈去。
【在 d***e 的大作中提到】
: 其实是因为最近送的蜡像，金正日看到老妈张开双臂，知道中国同志的意思是让他早点
: 去见他妈去。
c*e
26 楼
小B干爹真牛啊~~~~~~~~~~~
【在 m***h 的大作中提到】
: 好的
【在 m***h 的大作中提到】
: 好的
t*i
27 楼
哪个海？MM也在弯曲吗？
P*u
28 楼
顶一下我们poodle家族的
c*e
29 楼
对啊，在南湾，mm也在？
这个地方是point reyes national seashore 的kohoe beach
【在 t***i 的大作中提到】
: 哪个海？MM也在弯曲吗？
这个地方是point reyes national seashore 的kohoe beach
【在 t***i 的大作中提到】
: 哪个海？MM也在弯曲吗？
c*e
30 楼
谢谢mm啊！
【在 P*******u 的大作中提到】
: 顶一下我们poodle家族的
【在 P*******u 的大作中提到】
: 顶一下我们poodle家族的
l*e
31 楼
可爱！！！！！！！！！！！！！！！！亲亲！！！！！！
l*o
32 楼
哈哈， 让我想到那个点刹和抱死的区别
c*e
33 楼
回亲:*
【在 l*****e 的大作中提到】
: 可爱！！！！！！！！！！！！！！！！亲亲！！！！！！
【在 l*****e 的大作中提到】
: 可爱！！！！！！！！！！！！！！！！亲亲！！！！！！
c*e
34 楼
哪一条联系了这个？求详解:P
【在 l*****o 的大作中提到】
: 哈哈， 让我想到那个点刹和抱死的区别
【在 l*****o 的大作中提到】
: 哈哈， 让我想到那个点刹和抱死的区别
l*o
35 楼
关键词： 沙滩 怕水 :)
【在 c*********e 的大作中提到】
: 哪一条联系了这个？求详解:P
【在 c*********e 的大作中提到】
: 哪一条联系了这个？求详解:P
t*i
36 楼
是阿是阿，我发现南湾的同学还挺多的，怎么从来没有聚会呢？
【在 c*********e 的大作中提到】
: 对啊，在南湾，mm也在？
: 这个地方是point reyes national seashore 的kohoe beach
【在 c*********e 的大作中提到】
: 对啊，在南湾，mm也在？
: 这个地方是point reyes national seashore 的kohoe beach
t*i
37 楼
笑死。。。。
【在 l*****o 的大作中提到】
: 关键词： 沙滩 怕水 :)
【在 l*****o 的大作中提到】
: 关键词： 沙滩 怕水 :)
c*e
38 楼
哈哈，这个太赞了~~~~~~~~~~~我家的要这么拖属于抱死类型:DDDDDDDD
【在 l*****o 的大作中提到】
: 关键词： 沙滩 怕水 :)
【在 l*****o 的大作中提到】
: 关键词： 沙滩 怕水 :)
c*e
39 楼
是啊，要能聚聚多好呀！
【在 t***i 的大作中提到】
: 是阿是阿，我发现南湾的同学还挺多的，怎么从来没有聚会呢？
【在 t***i 的大作中提到】
: 是阿是阿，我发现南湾的同学还挺多的，怎么从来没有聚会呢？
相关阅读
对主人总是保护状态的狗怎么办带肥皮来骗包子咯,顺便推荐个新买的罐头求纽约新泽西地区的同学帮忙，顺便奔个四少妞妞和女儿帮忙看一下，不会是UTI前兆吧你们家猫咪都有什么特异功能？准备最早8月份开始养金毛 puppy 向大家请教猫吃的用来吐毛球的要叫什么名字？Rally比赛灰头土脸...还差点把A的小命搭上……有这样恨罐头的猫么！！！来福 (转载)继续奔猫之猫主子一岁生日怎麽过兽医归来【UPDATE】 急，有没有自己治疗猫外伤的办法大家知道petsmart给猫猫洗剪吹的价格嘛……4、6L更新pic夏天来了怎么样防院子里的兔子MAOMAO正在手术中 Update起来放羊啦有没有人对这个感兴趣笑死我了，mean kitty (转载)