nyoj 289-りんご

http://acm.nyist.net/JudgeOnline/problem.php?pid=289
りんご
時間制限:
3000 ms  |  メモリの制限:
65535 KB
難易度:
3
説明
ctestにはn個のリンゴがあり、容量vのリュックサックに入れます.i番目のりんごの大きさと値段をあげて、リュックサックに入れられるりんごの総価格の最大値を求めます.
入力
複数のテストデータがあり、各テストデータの最初の動作は2つの正の整数で、それぞれアップルの個数nとリュックサックの容量vを表し、n、vが同時に0の場合にテストを終了し、このとき出力しない.次のn行は、行ごとに2つの正の整数で、リンゴの大きさcと価格wをそれぞれ表すスペースで区切られています.すべての入力値の範囲は0以上1000以下です.
しゅつりょく
各テストデータに整数を出力し、リュックサックに入れることができるアップルの総価値を表します.
サンプル入力

3 3
1 1
2 1
3 1
0 0

サンプル出力

2

典型的なリュックサック問題ですね.以前はあまり分かりませんでした.今日はまた午後を見た.いい感じです.の
「前のi個の物品を容量vのリュックサックに入れる」というサブ問題は、i個目の物品の戦略(置くか置かないか)だけを考慮すれば、前のi−1個の物品のみを巻き込む問題に転化することができる.i番目のアイテムを置かないと、問題は「前のi-1アイテムを容量vのリュックサックに入れる」ことに変わり、価値はf[i-1][v].i番目のアイテムを置くと、問題は「前のi-1アイテムを残りの容量v-c[i]のリュックサックに入れる」ことに転化し、このとき得られる最大の価値はf[i-1][v-c[i]]に加え、i番目のアイテムを入れることで得られる価値w[i]である.
次の3つの方法.最後のタイムアウト:

#include
#include
#include
int m[1001][1001];
using namespace std;
int main() {
  int n, c;
  int w[1001], p[1001];
  while (cin >> n >> c && (n || c)) {
    memset (m, 0, sizeof(m));
    for (int i = 1; i <= n; i++) 
      cin >> w[i] >> p[i];
    for (int i = 1; i <= n; i++) {
      for (int j = 0; j <= c; j++) 
        if (j < w[i]) m[i][j] = m[i - 1][j];
        else m[i][j] = max(m[i - 1][j], m[i - 1][j - w[i]] + p[i]);
    }
    cout << m[n][c] << endl;
    
  }
}

#include
#include
//#include
using namespace std;
int main() {
  int n, c;
  int w[1001], p[1001];
  int m[1001];
  while (cin >> n >> c && (n || c)) {
    memset (m, 0, sizeof(m));
    for (int i = 1; i <= n; i++) 
      cin >> w[i] >> p[i];
    for (int i = 1; i <= n; i++) {
      for (int j = c; j >= w[i]; j--) 
        if (m[j - w[i]] + p[i] > m[j])
          m[j] = m[j - w[i]] + p[i];
    }
    cout << m[c] << endl;
    
  }
}

タイムアウトコード:

 
#include
#include
#include
using namespace std;
int w[1001], p[1001];
int f(int i, int j) {
  if (i < 0) return 0;
  if (j < w[i]) return f(i - 1, j);
  return max(f(i - 1, j), f(i - 1, j - w[i]) + p[i]);
}
int main() {
  int n, c;
  while (cin >> n >> c && (n || c)) {
    memset (w, 0, sizeof(w));
    memset (p, 0, sizeof(p));
    for (int i = 0; i < n; i++) 
      cin >> w[i] >> p[i];
    cout << f(n - 1, c) << endl;
  }
}