poj-1276
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
#include <stdio.h>
struct denomiationInfo {
int D;
int num;
};
typedef struct denomiationInfo denomiationInfo;
int getBinary01DenomiationInfo(denomiationInfo * originalDInfo, int N, int denomiationNum,
int * dInfo) {
int binary01DenomiationInfoNum = 0;
for (int i = 0; i < denomiationNum; i++) {
int dNum = (originalDInfo + i)->num;
int D = (originalDInfo + i)->D;
// printf("before, %d %d\n", dNum, D);
int j;
for (j = 1; dNum - (1<<j) + 1 >0; j++) {
dInfo[binary01DenomiationInfoNum++] = D*(1<<(j-1));
// printf("getBinary01DenomiationInfo %d %d\n", binary01DenomiationInfoNum-1, dInfo[binary01DenomiationInfoNum-1]);
}
dInfo[binary01DenomiationInfoNum++] = (dNum - (1<<j-1) + 1) * D;
}
return binary01DenomiationInfoNum;
}
void getBestCash(denomiationInfo * dInfo, int N, int denomiationNum) {
// int DP[102][100050] = {0};
int DP[100050] = {0};
int binary01DenomiationInfo[102] = {0};
int binary01DenomiationInfoNum = getBinary01DenomiationInfo(dInfo,
N, denomiationNum, binary01DenomiationInfo);
// printf("%d\n", binary01DenomiationInfoNum);
// for (int i = 0; i < binary01DenomiationInfoNum; i++) {
// printf("%d ", binary01DenomiationInfo[i]);
// }
// printf("\n");
for (int i = binary01DenomiationInfoNum - 1; i >= 0; i--) {
for (int j = N; j >= 0; j--) {
// printf("%d %d\n", i, j);
if (i == binary01DenomiationInfoNum - 1) {
if (binary01DenomiationInfo[i] > j) {
DP[j] = 0;
} else {
DP[j] = binary01DenomiationInfo[i];
}
} else if (j == 0) {
DP[j] = 0;
} else {
if (binary01DenomiationInfo[i] > j) {
continue;
// DP[j] = DP[j];
} else {
int takeIt = binary01DenomiationInfo[i] + DP[j-binary01DenomiationInfo[i]];
int noTakeIt = DP[j];
DP[j] = takeIt > noTakeIt ? takeIt : noTakeIt;
}
}
}
}
水DP, 思想是很普通的DP思想， 不过需要一些DP的高级处理技巧。
// for (int i = denomiationNum - 1; i >= 0; i--) {
// for (int j = 0; j <= N; j++) {
// if (i == denomiationNum - 1) {
// int beginValue = 0;
// for (int k = 1; k <= dInfo[i].num; k++) {
// beginValue += dInfo[i].D;
// if (beginValue > j) {
// DP[i][j] = beginValue - dInfo[i].D;
// break;
// }
// }
// } else {
// int BestValue = 0;
// for (int k = 0; k <= dInfo[i].num; k++) {
// if (j - k * dInfo[i].D >= 0) {
// int value = k * dInfo[i].D + DP[i+1][j - k * dInfo[i].D];
// BestValue = BestValue > value ? BestValue : value;
// } else {
// break;
// }
// }
// DP[i][j] = BestValue;
// }
// }
// }
printf("%d\n", DP[N]);
}
int main() {
int N = 0;
while(scanf("%d", &N) != EOF) {
int denomiationNum = 0;
scanf("%d", &denomiationNum);
if (denomiationNum <= 0) {
printf("0\n");
continue;
}
denomiationInfo dInfo[11];
int tmpD = 0;
int tmpNum = 0;
int validNum = 0;
for (int i = 0; i < denomiationNum; i++) {
scanf("%d %d", &tmpNum ,&tmpD);
if (tmpNum != 0) {
dInfo[validNum].D = tmpD;
dInfo[validNum].num = tmpNum;
validNum++;
}
}
if (N <= 0) {
printf("0\n");
continue;
}
if (validNum == 0) {
printf("0\n");
continue;
}
getBestCash(dInfo, N, validNum);
}
}一开始直接开的二维大数组， 按照多重背包直接开搞（在求每个DP值时遍历可能的取该面值的个数， 后来才注意， 输入的面值个数是能到1000的），果然TLE。
最开始还RE了几次， 后来才发现是处理输入时出了问题， 在输入面值总数为0时，此轮输入会提前结束，要处理下这个特殊情况.
看到discuss里, 有人提到这种最朴素的DP法会TLE， 就又复习了<背包九讲>， 以前没需求，没怎么看懂，现在带着目的性，明显有收获.
普通的搞法， 最后的时间复杂度会跟每个面值能取的个数成直接正比， 所以效率低。
九讲里介绍了一种比较高阶的表现技巧， 及用一系列的二进制综合表示对某一个面值可能的个数选择(假设总共Z个该面值的货币): 令这些个数分别为 1， 2的1次方， 2的2次方.. 2的k-1次方， 直到有 Z-2的k次方 +1 > 0. 1， 2的1次，... 2的 k-1 次， Z - 2的k次方 +1， 而1~Z之间的任何数和这个range的组合正好是一一对应的（这是一个数学上的技巧了） 。 这就意味着我们完全可以将 Z个面值为D的总金额(Z*D) 转换为 上面的一系列离散值 分别乘以D. 这样就把多重背包转化成了 0-1背包， 而因为用的是这种二进制分解法， 因此不会和普通的多重转01一样， 效率没有提升， 会从N 提升为 logN.
这一步除了带来多重转01外，还变相的增加了DP的层数（原来有N个面值，现在必定有>=N个面值）（其实也是空间换时间了， 多重求DP每次循环， 本质上是重叠子问题， 但是没有缓存结果， 而转01，则将缓存了）。结果还按照二维矩阵搞， 直接内存不够溢出了。
这样就又用上了九讲中的空间节省技巧， 直接把原来的二维压为一维.
这个技巧之前看九讲没领会，现在用多了， 就能理解了.
二维矩阵，除了第一层外， 其他层存储的其实都是临时信息， 最关键的是，某一层i的临时信息只会被i+1层用到，这样就可以理解压缩了.
在我用i层的信息得到i+1层的信息以后， 完全可以把i+1层的信息存储在i层的位置。因此，一维矩阵就够用了.
这里有个注意点,
求DP时的第二重循环，遍历0~N的值（二维的做法），一维用从N 到 0.
for (int j = N; j >= 0; j--) {
这么做的原因是:后面的递推方程：
takeIt() = binary01DenomiationInfo[i] + DP[i+1][j-binary01DenomiationInfo[i]];（一维）
int noTakeIt = DP[i+1][j];(二维)
takeIt = binary01DenomiationInfo[i] + DP[j-binary01DenomiationInfo[i]];（一维）
int noTakeIt = DP[j];(一维)
可以看到，D[i][j] 的值 受到了 D[i+1][j] 和 DP[i+1][j-binary01DenomiationInfo[i]]的影响,
而 binary01DenomiationInfo[i]是 >=0的，
因此，如果用一维数组，但是从0开始遍历N，就会出现在求D[j](第i层)时， DP[j-binary01DenomiationInfo[i]]的值已经被覆盖为了第i层的取值，
但我们这时候需要的是第i+1层的DP[j-binary01DenomiationInfo[i]].
因此，要从N开始降序到0.
DP题也做了一批了， 正好现在又复习九讲， 好好归纳总结下.
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |