樸素
#include <bits/stdc++.h>
using namespace std;
const int N = 1005;
int n, m;
int f[N][N];
int v[N], w[N], s[N];
int main()
{
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 * v[i] <= j && k <= s[i]; k ++ )
{
f[i][j] = max(f[i][j], f[i - 1][j - v[i] * k] + w[i] * k);//因為是在同一維上，所以用的是f[i][j]來作比較
}
}
}
cout << f[n][m] << endl;
return 0;
}
多重背包優化
把每種物品以2的平方來分組
（
1
，
2
，
4
，
8......
）
（1，2，4，8...... ）
（1，2，4，8......）
因為這些數可以湊出總個數以內的所有數所以可以這樣操作
比如$6（1，2，3）$這三個數可以湊數6以內的所有數，最后那個3是不足4的，所以單獨拿出來
比如9（1，2，4，2），也可以很明顯的發現可以湊出9以內的所有數，
所以把這些物品分組后，每組算作一個單獨的新物品，然后算出它們的體積和價值，最做一遍01背包即可，
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 10005; //注意陣列越界問題
int n, m;
int f[N], v[N], w[N];
int main()
{
cin >> n >> m;
int cnt = 0;
for (int i = 1; i <= n; i ++ )
{
int a, b, c; cin >> a >> b >> c;
int k = 1;
//分組操作
while (k <= c) //就是不能剛好減完
{
cnt ++;
v[cnt] = a * k;
w[cnt] = b * k;
c -= k;
k *= 2;
}
if (c > 0) //最后不足2的平方的數單獨拿出來放
{
cnt ++;
v[cnt] = c * a;
w[cnt] = c * b;
}
}
//01背包
for (int i = 1; i <= cnt; i ++ )
{
for (int j = m; j >= v[i]; j -- )
{
f[j] = max(f[j], f[j - v[i]] + w[i]);
}
}
cout << f[m] << endl;
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/384522.html
標籤：其他
上一篇：Nmap埠掃描工具
下一篇：西郵Linux2019面試題