s*t
2 楼
老是看电脑眼睛很干，请问最近滴眼液有deal吗？
还有戴隐形眼镜眼镜干用的滴眼液或者是tear的那种比较好用呢？
还有戴隐形眼镜眼镜干用的滴眼液或者是tear的那种比较好用呢？
z*3
3 楼
这题有最优解么？
f*w
4 楼
RA下个月的blink
s*5
5 楼
这不最basic的DP吗？
【在 i******t 的大作中提到】
: dp方法
【在 i******t 的大作中提到】
: dp方法
s*t
6 楼
请教一下具体应该怎么买呢？不会啊~
Y*f
7 楼
可以重复吗？如果允许重复的话就是bfs
不允许重复用dp，记录当前能够对应每个数的最少硬币数和最后一个硬币
【在 i******t 的大作中提到】
: dp方法
不允许重复用dp，记录当前能够对应每个数的最少硬币数和最后一个硬币
【在 i******t 的大作中提到】
: dp方法
d*n
8 楼
rebate之后免费，听说wg有4off胖子，在展板上，所以能倒赚。
再具体，加入ra club跟着学习。
给个包子吧。
【在 s******t 的大作中提到】
: 请教一下具体应该怎么买呢？不会啊~
b*7
9 楼
完全背包问题
f(i,v) = min{f(i-1,v), f(i-1,v - k[i])+1}
f(i,v) 用f(v)表示
初始f(v) = MAX_INT (v = 1,..., sum), f(0) = 0
for i = 0 ... m-1
for v = 1...sum
if v >= k[i] and f(v-k[i]) + 1 < f(v)
f(v) = f(v-k[i]) + 1
return f(sum)
参见：三种背包问题http://www.wutianqi.com/?p=539
f(i,v) = min{f(i-1,v), f(i-1,v - k[i])+1}
f(i,v) 用f(v)表示
初始f(v) = MAX_INT (v = 1,..., sum), f(0) = 0
for i = 0 ... m-1
for v = 1...sum
if v >= k[i] and f(v-k[i]) + 1 < f(v)
f(v) = f(v-k[i]) + 1
return f(sum)
参见：三种背包问题http://www.wutianqi.com/?p=539
r*7
10 楼
bfs怎么解？
【在 Y********f 的大作中提到】
: 可以重复吗？如果允许重复的话就是bfs
: 不允许重复用dp，记录当前能够对应每个数的最少硬币数和最后一个硬币
【在 Y********f 的大作中提到】
: 可以重复吗？如果允许重复的话就是bfs
: 不允许重复用dp，记录当前能够对应每个数的最少硬币数和最后一个硬币
j*7
11 楼
public static int minCoinsFor(int[] denom, int total) {
int[][] choice = new int[denom.length + 1][total + 1];
int[][] DP = new int[denom.length + 1][total + 1];
DP[denom.length][0] = 0;
for (int i = 1; i <= total; i++) {
DP[denom.length][i] = -1;
}
for (int i = denom.length - 1; i >= 0; i--) {
for (int j = 0; j <= total; j++) {
int min = -1;
for (int k = 0; k * denom[i] <= j; k++) {
int temp = DP[i + 1][j - k * denom[i]];
if (temp != -1) {
temp = temp + k;
if (min == -1) {
choice[i][j] = k;
min = temp;
} else if (temp < min) {
min = temp;
choice[i][j] = k;
}
}
}
DP[i][j] = min;
}
}
int min = DP[0][total];
if (min != -1) {
for (int i = 0; i < denom.length; i++) {
if (choice[i][total] != 0) {
System.out.print(choice[i][total] + ":" + denom[i] + "s
");
total = total - choice[i][total] * denom[i];
}
}
System.out.println();
}
return min;
}
int[][] choice = new int[denom.length + 1][total + 1];
int[][] DP = new int[denom.length + 1][total + 1];
DP[denom.length][0] = 0;
for (int i = 1; i <= total; i++) {
DP[denom.length][i] = -1;
}
for (int i = denom.length - 1; i >= 0; i--) {
for (int j = 0; j <= total; j++) {
int min = -1;
for (int k = 0; k * denom[i] <= j; k++) {
int temp = DP[i + 1][j - k * denom[i]];
if (temp != -1) {
temp = temp + k;
if (min == -1) {
choice[i][j] = k;
min = temp;
} else if (temp < min) {
min = temp;
choice[i][j] = k;
}
}
}
DP[i][j] = min;
}
}
int min = DP[0][total];
if (min != -1) {
for (int i = 0; i < denom.length; i++) {
if (choice[i][total] != 0) {
System.out.print(choice[i][total] + ":" + denom[i] + "s
");
total = total - choice[i][total] * denom[i];
}
}
System.out.println();
}
return min;
}
r*h
12 楼
不需要ls这么复杂啊，1D的经典多重背包问题
a = [1, 3, 5, 7, 9]
num = [9999 for i in range(30)]
num[0] = 0
for coin in a:
i = coin
while i<30:
if num[i-coin]+1 < num[i]:
num[i] = num[i-coin]+1
i = i+1
print(num)
a = [1, 3, 5, 7, 9]
num = [9999 for i in range(30)]
num[0] = 0
for coin in a:
i = coin
while i<30:
if num[i-coin]+1 < num[i]:
num[i] = num[i-coin]+1
i = i+1
print(num)
相关阅读
CVS or RA 冲照片能用ecb or upr么？求deal,麻烦各位帮忙建议了!这个rebate谁有啊转让 2 张 enfagrow $5 off 厂家coupon哪里能修电子词典？ (转载)CVS 有些巧克力75% OFF,有人知道couponnetwork吗？是不是骗人的？[交换]Enfamil买$40返$15的Rebate[求购]求WALGREENS的baby care coupon book，有pampers的求一张lowes 10% off coupon (转载)Rite Aid ThermacareCVS: FREE Frito Lay chipsSafeway: Hallmark card moneymaker this week（已经分了）有tx分这个啤酒rebate的吗？【amazon 20%和10off买卖专用帖】哪里买Burt's bees Res-Q Ointment 和 Baby bee all better bal (转载)这周ra有啥可买的？请问最近有谁在cvs phamacy fill prescription成功用过competitor coupon呢？谢谢Staples 20% off coupon give away (expires today)[求购]Simply Saline Adult Nasal Mist, Allergy and Sinus Giant Size, 4.25-Ounce