白準12865号:普通リュック

問題の説明

これは

201 knapsackという構造化アルゴリズムの問題である.

方法

Nのサイズが100の場合、完全なナビゲーションはタイムアウトになります.

2배낭의 남은 무게に基づいてアクセスする必要があります.

現在残っている重量がiのとき、すべてのものjは「私がかばんに入ったとき、価値がもっと大きいのか」と思っています.

バックパックの残り重量が7 kgの場合、3 kgのアイテムは「私の価値+(7-3)kgの最高価値」と「以前の7 kgの最高価値」を比較します.

dp

あたり最大重量が表示されます.

なぜ重い位置から探求するのですか?

の値は無効です.

3のテーブルはどうせ7より低い数字で、7から下に更新しても問題ありません.

正解

import java.util.*;

public class Main {
	static class material{ // 물건의 무게와 가치를 담기 위한 클래스
		int W,V;
		public material(int w, int v) {
			super();
			W = w;
			V = v;
		}
		@Override
		public String toString() {
			return "material [W=" + W + ", V=" + V + "]";
		}
	}
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		StringTokenizer st = new StringTokenizer(sc.nextLine()," ");
		int N = Integer.parseInt(st.nextToken());
		int K = Integer.parseInt(st.nextToken());
		material[] M = new material[N]; // 물건을 담을 배열
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(sc.nextLine()," ");
			M[i] = new material(Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));
		}
        
		int[] dp = new int[K+1]; // 여유공간이 0일때부터 K일때까지를 나타내는 dp배열

		dp[0] = 0; 
		for (int j = 0; j < N; j++) { // 물건
			for (int i = K; i >= M[j].W; i--) { // 남은 무게
				if(i-M[j].W<0)continue; // 여유공간보다 물건이 더 무거우면 패스
				dp[i] = Math.max(dp[i],dp[i-M[j].W]+ M[j].V); // 
                //i = 7, j물건의 무게 = 3, j물건의 가치 = 6이라고 할 때 
                //이전에 구한(==다른j로 구한) 7로 채울 수 있는 최댓값과 현재 j를 넣었을 때의 값을 비교합니다
                //j를 넣었을 때의 가치는 'j의 가치 + (i-j의 무게)일때 최적의 가치' 입니다
				
			}
		}
//		System.out.println(Arrays.toString(dp));
		System.out.println(dp[K]);
	}
	
}

その他

まちがった理由

はまずdpの点火式を設計していない.デザインはおろか、似たようなやり方にも近づけなかった.
余剰重量を使用する概念はありません.

ネット上の2次元配列で問題を解く場合は理解しにくい.

j番目のものを置くとき(jものの重さはjw)i-jw 2番目の値は理解できる、

どのラインのi-jw値を採用するか分かりません.私の概念では、各行のi-jw値を比較して、最低価格を取るべきです.

は,累積探索を理解していないためかもしれないが,j番目の最高値はjの重量とは限らない.

初期設計コードの反例

1 2
1 3
バッグに2キロの空き重量【1キロ、3元】のものが入っている場合
物は一つしか存在しないので、三元の結果があるはずです.一キロの物は一度入れて、一キロの空きスペースです.
私のアルゴリズムはそれを考えず、1 kgのものを2回だけ入れた結果、6元になりました.

逆ナビゲーションはなぜ重複を阻止しますか?

...大まかな説明方法を理解できる場所。

https://st-lab.tistory.com/141