这2.3最后一题属实是给我当头一棒了
负数体积01背包
#include<iostream>
#include<cstring>
#define x first
#define y second
using namespace std;
const int N = 105, M = 100005, INF = 0x3f3f3f3f;
int dp[2*M];
typedef pair<int, int> PII;
PII cow[N];
int n, m = M;//初始体积加一个偏移量
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> cow[i].x >> cow[i].y;
if(cow[i].x > 0) m += cow[i].x;
}
memset(dp, -0x3f, sizeof dp);
dp[M] = 0;
for (int i = 0; i < n; i++)
{
int v = cow[i].x, w = cow[i].y;
if (v > 0)
{
for (int j = m; j >= v; j--)
dp[j] = max(dp[j], dp[j - v] + w);
}
else
{
for (int j = 0; j <= m + v; j++)//注意这里上限是m+v
{//并且注意这里的遍历顺序,因为是负数,因此是正向遍历
dp[j] = max(dp[j], dp[j - v] + w);
}
}
}
int ans = 0;
for (int i = M; i <= m; i++)//只遍历S值为正的dp
if (dp[i]>= 0)ans = max(ans, i - M + dp[i]);
cout << ans << endl;
return 0;
}