C++学习---背包问题详解+配图解析

可参考https://blog.****.net/livelylittlefish/article/details/2186206

背包问题可以简述为，前i件物品有对应的重量w(i)和价值v(i)，要在满足不大于背包容量的情况下装入总价值最大的物品。

如输入

4 10

2 3 4 7

1 3 5 9

四件物品，重量分别为2 3 4 7，对应的价值分别为1 3 5 9，背包容量为10

最大价值表如下：

代码如下：

#include <iostream>
#include <vector>
using namespace std;
void display(vector<vector<int>> maxval, int num, int allwei, vector<int> wei)
{
vector<int> count;
count.resize(num + 1);
int j = allwei;
for (int i = num; i > 0; i--)
{
if (maxval[i][j] > maxval[i - 1][j])
{
count[i]++;
j -= wei[i];
}
}
for (int i = 0; i < count.size(); i++)
{
if (count[i] > 0)
cout << i << ' ' << '1' << endl;
}
}
void fun(int num, int allwei, vector<int> wei, vector<int> val, vector<vector<int>> dp)
{
for (int i = 1; i <= num; i++)
{
for (int j = 1; j <= allwei; j++)
{
dp[i][j] = dp[i - 1][j];
if (j >= wei[i])
{
int temp = dp[i - 1][j - wei[i]] + val[i];
if (temp > dp[i][j])
dp[i][j] = temp;
}


}
}
cout << dp[num][allwei] << endl;
display(dp,num,allwei,wei);
}
int main()
{
int allnumber, allweight;
vector<int> value;
vector<int> weight;
vector<vector<int>> maxvalue;
while (cin >> allnumber >> allweight)
{
vector <int> v(allweight + 1);
value.clear();
weight.clear();
maxvalue.clear();
value.resize(allnumber + 1);
weight.resize(allnumber + 1);
maxvalue.resize(allnumber + 1, v);
int num = allnumber;
for (int i = 0; i <= allnumber; i++)
maxvalue[i][0] = 0;
for (int i = 0; i <= allweight; i++)
maxvalue[0][i] = 0;
int i = 1;
while (num > 0)
{
cin >> weight[i] >> value[i];
num--;
i++;
}
fun(allnumber, allweight, weight, value, maxvalue);
}
return 0;
}