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ᵒᵛᵉᵧₒᵤ❤