多重背包问题 I
DFS暴力递归
#include<iostream>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int n,m;
int dfs(int x, int spV)
{
if(x > n) return 0;
//当前物品体积大于背包剩余体积直接看下一个
if(v[x] > spV){
return dfs(x + 1, spV);
} else {
//看看当前物品是否用完
if(s[x]){
s[x]--;
//继续用当前物品看看最后的值是多少
int taken = dfs(x, spV - v[x]) + w[x];
//获取到值之后把拿过的放回去
s[x]++;
//用下一个物品,看看最后的值是多少
int not_taken = dfs(x + 1, spV);
//比较拿当前物品的值大还是拿下一个物品的值大
return max(taken, not_taken);
} else {
return dfs(x + 1, spV);
}
}
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
scanf("%d%d%d",&v[i],&w[i],&s[i]);
int res = dfs(1, m);
cout << res << endl;
return 0;
}
记忆化搜索(能AC)
#include<iostream>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int n,m;
//体积,价值,物品数量
int mem[N][N][N];
int dfs(int x, int spV)
{
//如果有记录当前体积,价值,数量坐标的最大值的话直接返回
if(mem[x][spV][s[x]]) return mem[x][spV][s[x]];
int sum;
if(x > n) {
sum = 0;
} else {
//当前物品体积大于背包剩余体积直接看下一个
if(v[x] > spV){
sum = dfs(x + 1, spV);
} else {
//看看当前物品是否用完
if(s[x]){
s[x]--;
//继续用当前物品看看最后的值是多少
int taken = dfs(x, spV - v[x]) + w[x];
//获取到值之后把拿过的放回去
s[x]++;
//用下一个物品,看看最后的值是多少
int not_taken = dfs(x + 1, spV);
//比较拿当前物品的值大还是拿下一个物品的值大
sum = max(taken, not_taken);
} else {
//当前物品不能拿
sum = dfs(x + 1, spV);
}
}
}
//记录当前体积,价值,物品数量最优解
mem[x][spV][s[x]] = sum;
return sum;
}
int main()
{
cin >> n >> m;
for(int i = 1; i <= n; i++)
scanf("%d%d%d",&v[i],&w[i],&s[i]);
int res = dfs(1, m);
cout << res << endl;
return 0;
}
DP写法
#include <iostream>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int dp[N][N]; // 三维dp数组
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= m; j++) {
for (int k = 0; k <= s[i]; k++) {
if(k * v[i] <= j){ // 检查当前数量下是否可以放得下第i个物品
dp[i][j] = max(dp[i][j], dp[i-1][j - k * v[i]] + k * w[i]);
}
}
}
}
cout << dp[n][m] << endl;
return 0;
}
降维
#include <iostream>
using namespace std;
const int N = 110;
int v[N], w[N], s[N];
int dp[N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++)
cin >> v[i] >> w[i] >> s[i];
for (int i = 1; i <= n; i++) {
for (int j = m; j >= 0; j--) {
for (int k = 0; k <= s[i] && k * v[i] <= j; k++) {
dp[j] = max(dp[j], dp[j - k * v[i]] + k * w[i]);
}
}
}
cout << dp[m] << endl;
return 0;
}
好