动态规划——0-1背包问题

1、题目描述
 有N种物品，第i种物品的重量为wi，价值为vi，每种物品只有一个。背包能承受的重量为W。将哪些物品装入背包可使这些物品的总重量不超过背包容量，且价值总和最大？

输入：
第1行包含一个整数T，表示有T组测试用例。每组测试用例有3行，第1行包含两个整数
N; W(N1000; W 1000)分别表示物品的种数和背包的容量，第2行包含N个整数表示每种物
品的价值，第3行包含N个整数表示每种物品的重量。
输出：
每行一个整数，表示价值总和的最大值

举例：
输入--》1 
           5 10
           1 2 3 4 5
           5 4 3 2 1
输出--》14

2、分析：
每件物品均只有一件，可以选择装或者不装。
定义状态f[i][j],表示“前i个物品装进容量为j的背包可以获取最大 的价值”
状态方程：f[i][j] = max{ f[i-1][j], f[i-1][j-w[i]] + v[i]}

3、代码

#include <stdio.h>
#include <string.h>
#define MAXN 1000
#define MAXW 1000
int N, W;
int w[MAXN+1], v[MAXN+1]; /* 0 没有用*/
int f[MAXN + 1][MAXW + 1];
void dp() {
  int i, j;
  memset(f, 0, sizeof(f)); /*背包不一定要装满*/
  for(i = 1; i <= N; ++i) {
   for(j = 0; j <= W; ++j) {
     f[i][j] = f[i-1][j];
     if(j >= w[i]) {
      const int tmp = f[i-1][j-w[i]] + v[i];
      if(tmp > f[i][j]) f[i][j] = tmp;
     }
   }
 }
}
int main() {
 int i, T;
 scanf("%d", &T);
 while(T--) {
 scanf("%d %d", &N, &W);
 for(i = 1; i <= N; ++i) scanf("%d", &v[i]);
 for(i = 1; i <= W; ++i) scanf("%d", &w[i]);
 dp();
 printf("%d\n", f[N][W]);
 }
 return 0;
}