这个知识点人均应该都会(吧。
代码中有注释:
// todo 注意:此题 M 的大小并不是 1000,在我的代码中是乘了 3 * w!
#include <iostream>
#include <cstring>
#define int long long
using namespace std;
const int N = 30 + 7;
const int M = 1e6 + 7; // * 我不知道这个 bei 到底是多少,盲猜一个
int V, bei, n;
int flag[N][M];
int w[N], v[N], f[M];
int cnt;
int choose[N];
signed main()
{
//freopen("1.in", "r", stdin);
//freopen("1.out", "w", stdout);
ios::sync_with_stdio(false);
while(cin >> V >> bei)
{
memset(f, 0, sizeof(f));
cnt = 0;
memset(choose, 0, sizeof(choose));
cin >> n;
for(int i=1; i<=n; i++)
{
cin >> w[i] >> v[i];
w[i] *= bei * 3; // 题目要求
}
for(int i=1; i<=n; i++)
{
for(int j=V; j>=w[i]; j--)
{
if(f[j-w[i]]+v[i] > f[j])
{
f[j] = f[j-w[i]] + v[i];
flag[i][j] = 1; // ? 用 flag 表示第 num 个中,第 j 个是否可以被更新
}
}
} // 标准 01 背包
int num = n, times = V;
while(num > 0)
{
if(flag[num][times])
{
choose[++cnt] = num;
times -= w[num];
}
num--;
}
cout << f[V] << endl << cnt << endl;
for(int i=cnt; i>=1; i--)
cout << w[choose[i]] / (3*bei) << ' ' << v[choose[i]] << endl;
}
}
不知道哪里错了,WA 了,udebug 上是过了的/kk,求大佬看看。