【完全背包求方案数问题】AcWing1023.买书（赋练习题目）

【题目链接】活动 - AcWing

输入样例1：

20

输出样例1：

2

输入样例2：

15

输出样例2：

0

输入样例3：

0

输出样例3：

1

【代码】

//1023.买书——完全背包问题
 #include<bits/stdc++.h>
 using namespace std;
 int a[5]={0,10,20,50,100};
 int dp[5][1010];
 int main()
 {
 	int n;
 	cin>>n;
 	dp[0][0]=1;
 	for(int i=1;i<=4;i++)
 	{
 		for(int j=0;j<=n;j++)
 		{
 			dp[i][j]=dp[i-1][j];
 			if(j>=a[i]) dp[i][j]+=dp[i][j-a[i]];
 		}	
 	}	
 	cout<<dp[4][n];
 	return 0;
 } 

 【完全背包优化后代码】

//优化后
//1023.买书——完全背包问题
#include<bits/stdc++.h>
using namespace std;
int a[5]={0,10,20,50,100};
int dp[1010];
int main()
{
	int n;
	cin>>n;
	dp[0]=1;
	for(int i=1;i<=4;i++)
	{
		for(int j=a[i];j<=n;j++)
		{
			dp[j]+=dp[j-a[i]];
		}	
	}	
	cout<<dp[n];
	return 0;
} 

【相似题目——AcWing1371.货币系统】

【题目链接】 1371. 货币系统 - AcWing题库

输入样例：

3 10
1 2 5

输出样例：

10

 【代码及注释】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll dp[30][N];
int v[N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i];		
	}
	dp[0][0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<=m;j++)
		{
			dp[i][j]=dp[i-1][j];//不选择第i个物品
			if(j>=v[i]) dp[i][j]+=dp[i][j-v[i]]; 
		}
	}
	cout<<dp[n][m];
	return 0;
} 

【优化后代码】

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+10;
ll dp[N];
int v[N];
int main()
{
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>v[i];		
	}
	dp[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=v[i];j<=m;j++)
		{
			dp[j]+=dp[j-v[i]]; 
		}
	}
	cout<<dp[m];
	return 0;
}