2017-09-03 15:42:20
writer:pprp
01背包裸題,直接用一維陣列的做法就可以了
/*
@theme: 01 背包問題 - 一維陣列 hdu 2602
@writer:pprp
@begin:15:34
@end:15:42
@declare:最基本的01背包問題 POJ 3624
@error:最後取得是dp[M]不是 dp[M-1],然後注意資料範圍dp的資料範圍是M的範圍
@date:2017/9/3
*/
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
using namespace std;
const int maxn = 1010;
int dp[maxn];
int w[maxn], v[maxn];
int N, M;
int main()
{
freopen("in.txt","r",stdin);
ios::sync_with_stdio(false);
int cas;
cin >> cas;
while(cas--)
{
memset(dp,0,sizeof(dp));
cin >> N >> M;
for(int i = 0 ; i < N ; i++)
cin >> v[i];
for(int i = 0 ; i < N ; i++)
cin >> w[i];
for(int i = 0 ; i < N ; i++)
{
for(int j = M ; j >= w[i] ; j--)
{
dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
}
}
cout << dp[M] << endl;
}
return 0;
}
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsIyZuBnL1kzM5ITNzUTMx0iN0ADNyUjM3EzMwkDM3EDMy0SM4ITM2ETMvwVOwcTMwIzLcFDOyEjNxEzLcd2bsJ2Lc12bj5ycn9Gbi52YucTMwIzcldWYtl2Lc9CX6MHc0RHaiojIsJye.png)
代碼改變世界