首页 > 代码库 > POJ 3181 Dollar Dayz 01全然背包问题

POJ 3181 Dollar Dayz 01全然背包问题

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\n", lo[N]);
	}
	return 0;
}




POJ 3181 Dollar Dayz 01全然背包问题