Java算法-苹果(01背包问题)

苹果

时间限制：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
来源动态规划经典问题
import java.util.Scanner;

public class Main {
 //定义苹果静态内部类
 static class Apple {
  int c, w;

  public Apple(int c, int w) {
   // TODO Auto-generated constructor stub
   this.c = c;
   this.w = w;
  }
 }
 public static void main(String[] args) {
  Scanner sc = new Scanner(System.in);
  int n = sc.nextInt(), v = sc.nextInt();
  while (true) {
   if (n == 0 && v == 0)
    break;
   Apple ary[] = new Apple[n];
   int dp[] = new int[v+1];
   for (int i = 0; i < ary.length; i++) {
    ary[i] = new Apple(sc.nextInt(), sc.nextInt());
   }
   // 动态规划01背包
   for (int i = 0; i < ary.length; i++) {
    for (int j = dp.length - 1; j - ary[i].c >= 0; j--) {
     dp[j] = dp[j] > (dp[j - ary[i].c] + ary[i].w) ? dp[j]
       : (dp[j - ary[i].c] + ary[i].w);
    }
   }
   System.out.println(dp[v]);
   n=sc.nextInt();v=sc.nextInt();
  }
 }
}