0-1リュックサック問題のスーパーで選んだn個の品物

スーパーから選んだn個の品物は、それぞれの体積と価値があり、所定の容量のリュックサックがあるので、リュックサックに入れた品物に最大の価値の総和を持つようにプログラミングしてください(テストデータは唯一の解があることを保証します).0-1リュックサック問題解決構想a)リュックサック問題を抽象化(X 1,X 2,...,Xn,そのうちXiは0または1をとり,i番目の物品が選択または選択されないことを示す),Piはi番目の物品の価値を表し,Viはi番目の物品の体積(重量)を表す.b)モデルを確立し、すなわちmax(P 1 X 1+P 2 X 2+...+PnXn)を求める.c)制約条件、V 1 X 1+V 2 X 2+…+VnXn試験データ:サンプル1入力1000 5 800 2 400 5 300 5 400 3 200 2

0-1      ：（     ：n*C）

import java.util.Scanner;

public class BeiBao01 {
     



public static void main(String[] args) {
     

Scanner input = new Scanner(System.in);

    System.out.println("            ：");    

        int n = input.nextInt();

        int V = input.nextInt();

        

        int[] v = new int[n+1];

        int[] w = new int[n+1];

        

        int[][] f = new int[n+1][V+1];

        

        for (int i = 1; i <= n; i++) {
     

        System.out.println("    "+i+"         ：");

            v[i] = input.nextInt();

            w[i] = input.nextInt();

        }

        

        for (int i = 1; i <= n; i++) {
     

        for (int j = 0; j <= V; j++ ) {
     

        f[i][j] = f[i-1][j];

        if (j >= v[i]) {
     

        f[i][j] = Math.max(f[i][j], f[i-1][j-v[i]] + w[i]);   

        }

        }       

        }        

        int max = 0;

        for (int i = 0; i <= V; i++) {
     

        max = Math.max(max, f[n][i]);

        }

        System.out.println("       ："+max);

}

}