题意描述
思路
普通的背包问题复杂度为
O
(
n
W
)
O(nW)
O(nW)，但本题中的
W
W
W范围太大，所以不能使用这种方法，观察发现，本题中的
v
[
i
]
v[i]
v[i]比较小，所以我们可以用
f
[
i
]
[
j
]
f[i][j]
f[i][j]来表示从前
i
i
i种物品中选择，且价值为
j
j
j时的最小重量。得到转移方程：
f
[
i
]
[
j
]
=
f
[
i
−
1
]
[
j
]
f[i][j]=f[i-1][j]
f[i][j]=f[i−1][j]，
j
<
v
[
i
]
j<v[i]
j<v[i]
f
[
i
]
[
j
]
=
m
i
n
(
f
[
i
−
1
]
[
j
]
,
f
[
i
−
1
]
[
j
−
v
[
i
]
]
+
w
[
i
]
)
f[i][j]=min(f[i-1][j],f[i-1][j-v[i]]+w[i])
f[i][j]=min(f[i−1][j],f[i−1][j−v[i]]+w[i])，
j
≥
v
[
i
]
j≥v[i]
j≥v[i]
最后遍历一遍数组，取得满足条件得最大值即可
AC代码
#include<bits/stdc++.h>
#define x first
#define y second
#define PB push_back
#define mst(x,a) memset(x,a,sizeof(x))
#define all(a) begin(a),end(a)
#define rep(x,l,u) for(ll x=l;x<u;x++)
#define rrep(x,l,u) for(ll x=l;x>=u;x--)
#define sz(x) x.size()
#define IOS ios::sync_with_stdio(false);cin.tie(0);
using namespace std
;
typedef unsigned long long ull
;
typedef pair
<int,int> PII
;
typedef pair
<char,char> PCC
;
typedef long long ll
;
typedef pair
<ll
,ll
> PLL
;
const int N
=105;
const int M
=1e5+10;
const int INF
=0x3f3f3f3f;
const int MOD
=1e9+7;
int w
[N
],v
[N
],f
[N
][M
];
void solve(){
int n
,W
;cin
>>n
>>W
;
int mx
=-1;
rep(i
,1,n
+1) cin
>>w
[i
]>>v
[i
],mx
=max(mx
,v
[i
]);
f
[0][0]=0;
int bound
=mx
*n
;
rep(i
,1,bound
+1) f
[0][i
]=INF
;
rep(i
,1,n
+1){
rep(j
,0,bound
+1){
if(j
<v
[i
]) f
[i
][j
]=f
[i
-1][j
];
else f
[i
][j
]=min(f
[i
-1][j
],f
[i
-1][j
-v
[i
]]+w
[i
]);
}
}
ll ans
=0;
rep(i
,0,bound
+1) if(f
[n
][i
]<=W
) ans
=max(ans
,i
);
cout
<<ans
<<endl
;
}
int main(){
IOS
;
solve();
return 0;
}
