POJ 3181 Dollar Dayz 01完全背包問題
來源：程序員人生 發布時間：2014-09-16 15:03:11 閱讀次數：2523次
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;
}
生活不易，碼農辛苦
如果您覺得本網站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
