Tamflexの貯蔵庫

やる気のない備忘録

aoj DPL_1_B

0-1 Knapsack Problem | Aizu Online Judge
前にも書いたが0/1ナップサック問題には大きく分けて3つの解法がありそのうちdpである2つの解法で解いてみた

  1. dp[i][j] := (i番目の品物まで使った時の合計重さjを実現できる最大合計価値)
  2. dp[i][j] := (i番目の品物まで使った時の合計価値jを実現できる最小合計重さ)
  • 一個目
#include <bits/stdc++.h>

#define INF 1 << 30

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)

using namespace std;

int main()
{
  int n, W; cin >> n >> W;
  vector<int> v(n);
  vector<int> w(n);
  REP(i,n) cin >> v[i] >> w[i];
  vector<int> dp(10001,0);
  REP(i,n) DOWN(j, W, w[i])
    dp[j] = max(dp[j],dp[j-w[i]] + v[i]);
  cout << *max_element(dp.begin(),dp.begin()+W+1) << endl;
}
  • 二個目
#include <bits/stdc++.h>

#define INF 1 << 30

#define REP(i,n) for(int i=0;i<n;i++)
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define DOWN(i,b,a) for(int i=b;i>=a;i--)

using namespace std;

int main()
{
  int n, W; cin >> n >> W;
  vector<int> v(n);
  vector<int> w(n);
  REP(i,n) cin >> v[i] >> w[i];
  dp[0] = 0;
  REP(i,n) DOWN(j,100000,v[i])
    dp[j] = min(dp[j],dp[j-v[i]]+w[i]);
  DOWN(i,100000,0) if(dp[i] <= W)
  {
    cout << i << endl;
    break;
  }
}