AcWing 3442. 神奇的口袋
原题链接
简单
作者:
zhaoxi
,
2022-02-24 21:49:45
,
所有人可见
,
阅读 323
/*
这道题也是一道背包问题,只不过f[i][j]数组的值以前表示的是价值最大,现在表示在前i个物品中选,
体积正好等于j的选法之和,这时候就与w[]无关了,那么在状态转移方程书写的时候,左边表示不取第i
个物品且体积正好等于j,个数为f[i - 1][j],右边还是表示包含第i个物品,那么表示个数就和去除第i个
物品之后f[i - 1][j - v[i]]表示的个数相同,并且这时候是二者取和,因为表示的是不同的取法,一个包含第i
个物品,一个不包含第i个物品。
f数组的初始化也和01背包问题不大相同,以前是体积不超过j,且选取的物品不超过i的最大价值,当i=0的时候
表示什么都没选,自然最大价值就是0
而现在是表示前i个物品选择之后,体积正好等于j的选法之和,f[0][0]表示什么都没选的时候,体积正好等于0,
这是这种状态下唯一的一种选法,但是f[0][1]....f[0][40]就表示什么都不选的情况下体积等于1-40的情况,没有
一种选法会是这样,因此为0。
*/
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50;
int f[N][N];
int v[N];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> v[i];
}
f[0][0] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = 0; j <= 40; j ++) {
f[i][j] = f[i - 1][j];
if (j >= v[i])
f[i][j] = f[i][j] + f[i - 1][j - v[i]];
}
}
cout << f[n][40] << endl;
return 0;
}
#include <iostream>
#include <cstring>
using namespace std;
const int N = 50;
int f[N];
int v[N];
int n;
int main() {
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> v[i];
}
f[0] = 1;
for (int i = 1; i <= n; i ++) {
for (int j = 40; j >= v[i]; j --) {
f[j] = f[j] + f[j - v[i]];
}
}
cout << f[40] << endl;
return 0;
}