C++：背包问题习题

1. 货币系统

1371. 货币系统 - AcWing题库

给定 V 种货币（单位：元），每种货币使用的次数不限。

不同种类的货币，面值可能是相同的。

现在，要你用这 V 种货币凑出 N 元钱，请问共有多少种不同的凑法。

解题思路

我们两层循环分别枚举到第i种物品了，价值为j

如果枚举的价值大于当前枚举物品的价值就将f[i][j]的值赋为f[i][j-w[i]].这个值记录用w[i]凑到j的方法数量

不选的方法与f[i-1][j]的值相同。即不用w[i]凑到j的方法

AC代码

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>using namespace std;int v,n;
long long w[30];
long long f[30][10010];//前i种物品选择价值为j的方案数
int main()
{scanf("%d%d",&v,&n);for(int i=1;i<=v;i++){scanf("%d",&w[i]);}f[0][0]=1;for(int i=1;i<=v;i++){for(int j=0;j<=n;j++){if(j>=w[i])//选了{f[i][j]=f[i][j-w[i]];//凑f[i][j-w[i]](即少选一次w[i]的方法) 有几个方法，就是用w[i] 来凑到j的方法}//没选f[i][j]+=f[i-1][j];//加上没有这个i的方法,即不用w[i]来凑到j的方法}}printf("%lld",f[v][n]);return 0;
}

2. 01背包

2. 01背包问题 - AcWing题库

有 N件物品和一个容量是 V 的背包。每件物品只能使用一次。

第 i 件物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

解题思路

两层循环分别来枚举，到第i个物品，体积不小于j

如果j小于v[i]（v这个数组用来记录i个物品的体积，w数组用来记录价值）那只能不拿，价值就是不选i体积为j的价值

如果不小于就可以选择拿还是不拿，将拿了第i个物品体积才到j与不拿这个物品体积就到j的价值进行比较取较大值

AC代码

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int N, V;
int v[1010];
int w[1010];
int f[1010][1010];//前i件物品中，寻找不超过j个体积的最大价值
int main()
{scanf("%d%d", &N, &V);for (int i = 1; i <= N; i++){scanf("%d%d", &v[i], &w[i]);}for(int i=1;i<=N;i++)//前{for(int j=0;j<=V;j++)//体积{if(j<v[i])//不能拿{f[i][j]=f[i-1][j];//与没i是一样的，取值为不选第i件物品体积为j的最大价值}else//可以拿{f[i][j]=max(f[i-1][j-v[i]]+w[i],f[i-1][j]);//比较不拿第i件物品体积达到j与拿了第i件物品体积达到j谁更大}}}printf("%d\n", f[N][V]);return 0;
}

3. 完全背包

有 N 种物品和一个容量是 V 的背包，每种物品都有无限件可用。

第 i 种物品的体积是 vi，价值是 wi。

求解将哪些物品装入背包，可使这些物品的总体积不超过背包容量，且总价值最大。
输出最大价值。

解题思路

与01背包不同的是完全背包的每一种都可以无限选择，所以它选择第i个不用使i-1后再统计j-v[i]，因为之前可能使用过i了没使用(或使用了不如不用)那f[i][j-v[i]]也在之前初始化为了f[i-1][j-v[i]]

AC代码

#include<iostream>
#include<cstring>
#include<cstdio>using namespace std;int N,V;
int v[1010];
int w[1010];int f[1010][1010];int main()
{scanf("%d%d",&N,&V);for(int i=1;i<=N;i++){scanf("%d %d",&v[i],&w[i]);}for(int i=1;i<=N;i++)//枚举第i件物品{for(int j=0;j<=V;j++){if(j<v[i])//不能放{f[i][j]=f[i-1][j];//统计没放的}else//能放f[i][j]=max(f[i-1][j],f[i][j-v[i]]+w[i]);//没放这一次的价值，即选了k-1次i物品的价值}}cout<<f[N][V]<<endl;return 0;
}

4. 砝码称重

你有一架天平和 N 个砝码，这 N 个砝码重量依次是 W1,W2,⋅⋅⋅,WNW1,W2,···,WN。

请你计算一共可以称出多少种不同的正整数重量？

注意砝码可以放在天平两边。

解题思路

两层循环，枚举第i个砝码，能否凑成j的重量，存储值为布尔类型

一个砝码有三种情况，放在天平右边(看当前重量减去这个砝码重量是否能凑成(取绝对值，因为这边超过另一半，超过的重量也成立))，放在左边(同上不过是加上)与不放(看上一个可不可以即可)，只要有一种可以就能凑成。

将0个砝码，0重量初始化为true，但最后累计时不能算上，因为只统计正整数，0不是

AC代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>using namespace std;int N;
int v[110];bool f[110][200010];int main()
{scanf("%d",&N);int sum=0;for(int i=1;i<=N;i++){scanf("%d",&v[i]);sum+=v[i];}f[0][0]=true;//0肯定能凑出来，什么也不放就行for(int i=1;i<=N;i++)//第i个{for(int j=0;j<=sum;j++)//凑j的重量，能否凑成{//1如果不放就能达到j这个重量那肯定可以，2如果放到左边看不放之前有没有这个重量f[i][j]=f[i-1][j]|f[i-1][j+v[i]]|f[i-1][abs(j-v[i])];//不放和放左边和放右边}}int res=0;for(int i=1;i<=sum;i++)//i不能从0开始因为0不是正整数{if(f[N][i])res++;}printf("%d",res);return 0;
}

这篇就到这里啦（づ￣3￣）づ╭❤ ～(๑′ᴗ‵๑)Ｉ Lᵒᵛᵉᵧₒᵤ❤