POJ 3181 Dollar Dayz 01完全背包问题
来源：程序员人生 发布时间：2014-09-16 15:03:11 阅读次数：2338次
01完全背包问题。
主要是求有多少种组合。二维dp做的人多了，这里使用一维dp就可以了。
一维的转换方程：dp[j] = dp[j-i] + dp[j];其中i代表重量，j代表当前背包容量。
意思就是dp[j-i] 代表j-i背包重量的时候最多的组合数，那么如果到了背包容量为j的时候，就是可以把第i个物品装进背包，那么就有dp[j-i]种装法，
如果没有i物品之前，那么容量为j的时候组合数是dp[j]；
那么当有i物品，且容量为j的时候，那么组合数就是dp[j-i] + dp[j];
二维可以转为一维dp的特点：
1 不需要利用当前行之前的数据； 就是填表的时候是先填写列，然后填写下一行；当填写当前行的时候，只需要一行记录数据即可；当前列的数据可以立即读出，立即覆盖。
2 或者可以逆向填表；当需要利用当前行前几列的数据的时候，可以考虑从后面列开始填表
不过本题还多了一个知识点，就是需要处理大数，使用一般数组处理应该也是可以的，不过根据本题特点，可以只使用两个long long存储结果。
#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <limits.h>
#include <stack>
#include <queue>
#include <set>
#include <map>
using namespace std;
const int MAX_N = 1001;
int N, K;
long long hi[MAX_N], lo[MAX_N];
const long long MOD = 1E18;
int main()
{
while (~scanf("%d %d", &N, &K))
{
memset(hi, 0LL, sizeof(long long) * (N+1));
memset(lo, 0LL, sizeof(long long) * (N+1));
lo[0] = 1LL;
for (int i = 1; i <= K; i++)
{
for (int j = i; j <= N; j++)
{
hi[j] = hi[j-i] + hi[j];
hi[j] += (lo[j-i] + lo[j]) / MOD;
lo[j] = (lo[j-i] + lo[j]) % MOD;
}
}
if (hi[N] > 0LL) printf("%I64d", hi[N]);
printf("%I64d
", lo[N]);
}
return 0;
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
