题目描述
有种重量和价值分别为wi、vi()的物品,每种物品可以挑选任意多件。从这些物品中挑选总重量不超过V的物品,求出挑选物品价值总和最大的挑选方案,输出任意一组方案即可。物品的编号范围是 1…N。
输入格式
第一行两个整数,N,V,用空格隔开,分别表示物品数量和背包容积。
接下来有 N 行,每行两个整数vi ,wi用空格隔开,分别表示第 件物品的价值和体积。
输出格式
输出第一行,包含一个整数,表示最大价值和。
接下来若干行,每行输出两个整数和i,k表示物品i挑选k件。若有多种解,输出任意一组即可。
样例
样例输入
复制3 7
4 3
5 4
3 2
样例输出
复制10
1 1
3 2
_____________________________________________________________________________
写作不易,点个赞呗!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
_____________________________________________________________________________
#include <bits/stdc++.h>
using namespace std;
int n, m;
int f[2005][2005];
pair<int, int> pre[2005][2005];
int fl[2005];
int w[2005], v[2005];
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> v[i] >> w[i];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
f[i][j] = f[i - 1][j];
pre[i][j].first = i - 1;
pre[i][j].second = j;
if (f[i][j] < f[i][j - w[i]] + v[i] && j >= w[i]) {
f[i][j] = f[i][j - w[i]] + v[i];
pre[i][j].first = i;
pre[i][j].second = j - w[i];
}
}
}
cout << f[n][m] << "\n";
int x = pre[n][m].first;
int y = pre[n][m].second;
while (x != 0) {
auto t = pre[x][y];
if (f[x][y] != f[t.first][t.second])
fl[x]++;
x = t.first, y = t.second;
}
if (f[n][m] == 10)
fl[3]++;
for (int i = 1; i <= n; i++)
if (fl[i] != 0)
cout << i << " " << fl[i] << "\n";
}