背包问题练习2

【算法详解】背包问题的问法变化_背包问题问法的变化-CSDN博客背包求方案数的一系列模板可以得到思路。

P5365 英雄联盟P5365 [SNOI2017] 英雄联盟 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题解：首先这里的要求是方案数至少大于某个数，并且花费是最少的。所以我们这里需要的一个操作就是背包问题求方案数，但是我们如何知道金额的大小，就是通过一维背包的数组下标就可以看到。如果方案数大于等于要求的方案数，那么就可以输出dp数组的下标就是最终答案。由于我们可以看到题解中方案数是根据皮肤选取的个数来进行乘法运算。所以说明方案数是乘法有关系并且要和皮肤数量挂钩，所以再二层循环下面再套一层循环用来枚举每一个英雄用了多少个皮肤，再进行相乘这就是状态转移方程，f[j] = max(f[j],f[j-x*c[i]]*x)然后就是需要看背包的第二层循环的数量就是多少钱，我们可以看到对于这个来说就把全部皮肤的钱都加上就是总数。

#include<bits/stdc++.h>
using namespace std;
constexpr int N = 1000010;
long long n,m,k[N],c[N],dp[N],qm;
void solve(){
	cin>>n>>m;
	for(int i =1;i<=n;i++) cin>>k[i];
	for(int i = 1;i<=n;i++){
		cin>>c[i];
		qm+=k[i]*c[i];//钱的总数
	}
	dp[0] = 1;
	for(int i = 1;i<=n;i++){
		for(int j = qm;j>=0;j--){//只能选一次01背包
			for(int x = 1;x<=k[i];x++){//皮肤个数
				if(j>=x*c[i]){
					dp[j] = max(dp[j],dp[j-c[i]*x]*x);
				}
			}
		}
	}
	for(int i = 1;i<=qm;i++){
		if(dp[i]>=m){//找到大于等于的方案数
			cout<<i;//输出下标。
			return;
		}
	}
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}

P1077 摆花P1077 [NOIP2012 普及组] 摆花 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

思路：首先这个是有m个花，然后求的是一共多少种摆花方案，所以这也是求方案数，求的是可行方案数，所以dp数组求的是方案数，所以需要将dp[0] = 1，然后花有两种，并且每个花只能选一次，一开始把这个看成了一个多重背包的问题，但是由于水平比较低只会求01背包的方案数问题，所以就是说我可以把每一个花看成一个数，就是再01背包的情况下再套一层循环，但是这一层循环的是边界是min(a[i],j)就是不能超过当前的花盆数，并且不能超过这种花的花盆数，所以两者取最小就可以。然后由于这是可行方案数。我们可以看对于对于第i种花有了j盆，所以第i种花的摆放就是可能摆了0，1，2，3,….min(ai,j)盆。所以这些都是可能的情况，所以我们可以得到fij = (fi-1j+fi-1j-1+...fi-1,j-min(ai,j))。这个可以看一下顶上的文章求可行方案数。

代码:

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
using namespace std;
constexpr int N = 110;
constexpr int mod = 1e6+7;
int n,m,a[N];
int dp[N];
void solve(){
	cin>>n>>m;
	for(int i = 1;i<=n;i++) cin>>a[i];
	dp[0]= 1;
	for(int i = 1;i<=n;i++){
		for(int j = m;j>=0;j--){
			for(int k = 1;k<=min(a[i],j);k++){
				dp[j]= dp[j-k]+dp[j];
				dp[j] %= mod;
			}
		}
	}
	cout<<dp[m]%mod;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}

P2347P2347 [NOIP1996 提高组] 砝码称重 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

很老的题目，首先范围给死，六个砝码重量，然后会有输入的案例是每个砝码的重量，那么就是说这是个多重背包的问题，所以可以拆成多个01背包，因为数据量不大就用朴素的多重背包的解发，因为要求输出的是不同重量的个数，然后总重量就是每一个砝码重量加起来，所以求01背包求可行方案数，所以只要那个重量有方案数就可以。求可行方案数就是用顶上的文章的方法即可。

#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<map>
#include<vector>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<string>
using namespace std;
constexpr int N = 1e5+10;
int num[10] = {1,2,3,5,10,20};
int dp[N],a[N];
void solve(){
	int sum = 0;
	for(int i = 1;i<=6;i++){
		cin>>a[i];
		sum+=a[i]*num[i-1];
	}
	int ans = 0;
	dp[0] = 1;
	for(int i = 1;i<=6;i++){
		for(int j = sum;j>=0;j--){
			for(int k = 1;k<=a[i];k++){
				if(j>=num[i-1]*k){
					dp[j]+=dp[j-num[i-1]*k];
				}
			}
		}
	}
	for(int i =1;i<=sum;i++){
		if(dp[i]) ans++;
 	}
	cout<<"Total="<<ans;
}

int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	solve();
}