題目
給定 V 種不同面值的貨幣（單位：元），每種貨幣使用的次數不限，
現在，要你用這 V 種貨幣湊出 N 元錢，請問共有多少種不同的湊法，
輸入格式
第一行包含兩個整數 V 和 N，
接下來的若干行，將一共輸出 V 個整數，每個整數表示一種貨幣的面值，
輸出格式
輸出一個整數，表示所求總方案數，
資料范圍
1≤V≤25,
1≤N≤10000
輸入樣例：
3 10
1 2 5
輸出樣例：
10
二維DP
閆氏DP分析法：
狀態表示： f[i][j] 表示 從前i種貨幣中選，且總價值恰好為j的所有選法集合的方案數，
那么f[n][m]就表示表示 從前n種貨幣中選，且總價值恰好為m的所有選法集合的方案數，即為答案，
集合劃分：
按照第i種貨幣可以選 0個,1個，2個，3個，，，，k個劃分集合 f[i][j]，其中k*w[i] <= j,也就是說在背包能裝下的情況下，列舉第i種貨幣可以選擇幾個，
狀態計算：
f[i][j] = f[i-1][j]+f[i-1][j-w[i]]+f[i-1][j-2*w[i]],,,,,,+f[i-1][j-k*w[i]] .
ac代碼
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 30,M = 1e4 +10;
long long f[N][M]; // 方案數很大使用long long 來存
int w[N];
int main()
{
int n,m;
cin>>n>>m;
for(int i = 1; i <= n; i++) cin>>w[i];
f[0][0] = 1; // 使用0種貨幣，湊0元錢,也是一種方案
for(int i = 1; i <= n; i++)
for(int j = 0; j <= m; j++)
{
for(int k = 0; k*w[i] <= j; k++)
f[i][j] += f[i-1][j-k*w[i]];
}
cout<<f[n][m]<<endl;
return 0;
}
一維DP
考慮優化
v代表第i件物品的體積
f[i][j] = f[i-1][j] + f[i-1][j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])
f[i][j-v] = f[i-1,[j-v]+f[i-1][j-2v]+,,,,,+f[i-1][j-kv])
因此：
f[i][j] = f[i-1][j]+f[i][j-v])
圖示：
去掉一維：
狀態計算為： f[j] = f[j] + f[j-v]
ac代碼
#include<iostream>
#include<cstdio>
using namespace std;
const int N = 1e4 + 10;
long long f[N];
int main()
{
int m,n;
cin>>n>>m;
f[0] = 1; //初始化 f[0][0] = 1
for(int i = 1; i <= n; i++)
{
int v;
cin>>v;
for(int j = v; j <= m; j++)
f[j] += f[j-v]; // 狀態計算方程
}
cout<<f[m]<<endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/251834.html
標籤：區塊鏈