スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

なんとなく

なんとなくナップザック問題を解いてみる
AOJ0042
動的計画法のいい復習
再帰とかよくわかんないんで漸化式で解いていくスタイル


import java.util.Scanner;

public class Main {
public static void main(String[] args) {
int W,n;
Scanner sc = new Scanner(System.in);
int Case = 1;
while(true){
W = sc.nextInt();//入力データ数読み込み
if(W==0){break;}
n = sc.nextInt();//入力データ数読み込み
int[] w = new int[n+1];
int[] v = new int[n+1];
for(int i=0; i String[] s = sc.next().split(",");
v[i] = Integer.parseInt(s[0]);
w[i] = Integer.parseInt(s[1]);
}
int[][] dp = new int[n+1][W+1];
int maxV = Integer.MIN_VALUE;
int minW = Integer.MAX_VALUE;

for(int i =n-1; i>=0; i--){
for(int j =0; j<= W; j++){
if(j < w[i]){
dp[i][j]=dp[i+1][j];
}else{
dp[i][j] = Math.max(dp[i+1][j],dp[i+1][j-w[i]]+v[i]);
if(maxV < dp[i][j]){
maxV = dp[i][j];
minW = j;
}
else if(maxV == dp[i][j]){
minW = Math.min(minW, j);
}
}
}
}
System.out.println("Case " + Case++ + ":\n" + maxV + "\n" + minW);
}
}
}
スポンサーサイト
最新記事
カウンター
月別アーカイブ
カテゴリ
リンク
RSSリンクの表示
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。