//01 背包问题
//对于每个物品,有选和不选两个选项
#include<iostream>
using namespace std;
#define N 3000
int arc[N][N];//arc集合,第一个N表示目前物品数量,第二个N表示当前背包容积,arc[][]集合表示在第i个物品容积为j的情况下
//背包价值的最大值
int w[N];//每个物品重量
int va[N];//每个物品价值
int n, v;//物品个数及背包容积
int main()
{
cin >> n >> v;
for (int i = 1; i <= n; i++)
{
cin >> w[i] >> va[i];
}
for(int i=1;i<=n;i++)
for (int j = 1; j <= v; j++)
{
if (w[i] > j)arc[i][j] = arc[i - 1][j];//如果当前物品体积大于j,则不放入
else
arc[i][j] = max(arc[i - 1][j], arc[i - 1][j - w[i]] + va[i]);//比较不放入和放入两个选择的价值
//第二个意思是先将当前物品除开(物品数量-1及重量-w[i]),此时的arc就是除去当前物品后背包里的最大价值,再加上当前物品的价值,与
//不放物品时的价值相比较,取最大价值
}
cout << arc[n][v];
return 0;
}
7 01背包问题优化
//01背包问题优化
//二维变一维
//当没改变arc[i]的数据时,arc[i]中的数据即为上一层的数据,当改变时就覆盖arc[i]中的数据,因为只会用到前一层的数据,
//相当于一个一位数组中贮存了两行的数据,在一次循环中未改变的为继承了上一层的数据
#include<iostream>
using namespace std;
#define N 2000
int arc[N];
int va[N];
int w[N];
int n, v;
int main()
{
cin >> n >> v;
for (int i = 1; i <= n; i++)
{
cin >> w[i] >> va[i];
}
for(int i=1;i<=n;i++)
for (int j = v; j >= w[i]; j--)//倒着循环,因为会用到前面的数据,正着循环会将数据覆盖,当j<当前物品重量就不放,保留上一层状态
{
arc[j] = max(arc[j], arc[j - w[i]] + va[i]);//判断不放和放的价值
}
cout << arc[v];
return 0;
}