题目描述
给定n元钱,四本书,书的价格,求有多少种方案
样例
f[i][j]所有只从前i本书中选,且总价钱恰好是j的方案
f[i][j]:
(1)不选第i个数的选法f[i-1][j]
(2)选第i个数的所有选法f[i-1][j-v[i]]
f[i][j]=f[i-1][j]+f[i-1][j-v]+f[i-1][j-2v]+……f[i-1][j-v*s]
f[i][j-v]=f[i-1][j-v]+f[i-1][j-2v]+……+f[i-1][j-v*s]
所以f[i][j]=f[i-1][j]+f[i][j-v]
没有优化之前
C++ 代码
//书可以买多本(多重背包)
#include <iostream>
using namespace std;
const int N = 1100;
int f[5][N];
//f[i][j]代表只取前i本书,总钱数不超过j的方案数
int v[5] = {0,10,20,50,100};
int main(){
int n;//总钱数
scanf("%d",&n);
f[0][0] = 1;
for(int i=1;i<=4;i++){
for(int j=0;j<=n;j++){
f[i][j] = f[i-1][j];
if(j>=v[i]) f[i][j] += f[i][j-v[i]];
}
}
cout<<f[4][n]<<endl;
return 0;
}