동적 계획 알고리즘 - 가방 문제 출력 최 적 화 된 패키지 의 물체

최근 에 동적 계획 알고리즘 을 배우 고 있 는데 인터넷 자 료 는 수출 에 관 한 상세 한 정 보 를 가장 잘 풀 지 못 해서 자신 에 게 작은 임 무 를 주 었 습 니 다.고민 하 는 시간 이 오래 되 었 지만 알고리즘 에 대한 이 해 를 강화 하여 즐 거 웠 습 니 다.
가방 문제 요약: 용량 이 m 인 가방 을 알 고 있 습 니 다. 현재 무게 가 다른 가치 의 물품 이 있 습 니 다. 가방 용량 제한 하에 어떻게 이익 을 극 대화 할 수 있 는 지 물 어보 세 요.
알려 진 조건:                번호:      0  1  2 3  4 5  6 7  8   9  10 11 12 13
아 이 템 배열:  int[] w = { 0, 3, 4, 5 ,6,9,10,8,12,11,13,14,15,16};
아 이 템 가치 배열           int[] p = { 0, 4, 5, 6 ,7,8,9,10,11,10,12,15,17,18};
문제 분석: 큰 문 제 를 수많은 작은 문제 로 나 눌 수 있다.가방 용량 이 0 ~ 2 일 때 아 이 템 을 안 으로 넣 으 면 내 려 놓 을 수 있 는 것 이 없다 고 가정 합 니 다.
가방 용량 이 3 이 라 고 가정 하면 아 이 템 은 두 가지 상태 가 있 습 니 다. 1, ① 번 을 2, ① 번 에 넣 고 넣 지 않 습 니 다.최 적 화 된 기록 을 구하 다 result [3, 1]
가방 용량 4  아 이 템 은 이 몇 가지 상태 가 있 습 니 다. 1. ② 번 을 넣 고 현재 의 최 적 화 를 더 하여 가방 에서 ① 번 아 이 템 의 남 은 무게 의 최 적 화 된 남 은 용량 4 - w [2] = 0 을 제거 하 십시오.
      2 、 ② 번 은 넣 지 않 습 니 다.① 번 에 넣 는 최 적 화 를 구하 고 result [4, 1]
비교적 큰 값 을 비교 해 내다.
………………………………………………
가방 용량 [m]
int res1 = result[tempI-w[tempJ], tempJ-1] + p[tempJ];//int res2 = results [tempI, tempJ - 1]; / /결과 [tempI, tempJ] = Math. Max (res1, res2) 를 넣 지 않 음;

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace   _    _
{
    class Program
    {
        public static int[,] result;
        public static List best;//       
        public static int TotalWeight;//      
        static void Main(string[] args)
        {
            int m = 0;
            int.TryParse(Console.ReadLine(), out m);
            int[] w = { 0, 3, 4, 5 ,6,9,10,8,12,11,13,14,15,16};
            int[] p = { 0, 4, 5, 6 ,7,8,9,10,11,10,12,15,17,18};
            result = new int[m + 1, w.Length];
            best = new List();
            Console.WriteLine("      ：" + BottomUp(m, w.Length - 1, w, p));
            getList(w.Length, m, w);
            Console.Write("   ："+TotalWeight);
            for (int i = 0; i < best.Count; i++) {
                Console.Write("   ："+w[best[i]]+"  ："+p[best[i]]);
            }
            Console.ReadKey();
        }

        /// 

        ///         
        /// 
        ///     
        ///     
        ///     
        ///     
        /// 
        public static int UpDown(int m,int i, int[] w, int[] p) {
            if (m == 0 || i == 0)
            {
                return 0;
            }
            if (result[m, i] != 0) {
                Console.WriteLine(i+" "+w[i]+" "+p[i]);
                return result[m, i];
            }
            if (w[i] > m)
            {
                result[m, i] = UpDown(m, i - 1, w, p);
                return result[m, i];
            }
            else {
                int maxValue1 = UpDown(m - w[i], i - 1, w, p) + p[i];//  
                int maxValue2=UpDown(m, i - 1, w, p);//   
                result[m, i] = Math.Max(maxValue1, maxValue2);
                return result[m, i];
            }
        }
        public static int BottomUp(int m,int i,int[] w,int[] p) {
            if (result[m, i] != 0) {

                return result[m, i];
            }

            for (int tempI = 1; tempI <= m; tempI++) {
                for (int tempJ = 1; tempJ <= i; tempJ++)
                {
                    if (result[tempI, tempJ] != 0) continue;
                    if (w[tempJ] > tempI)
                    {
                        result[tempI, tempJ] = result[tempI, tempJ-1];
                    }
                    else {
                        int res1 = result[tempI-w[tempJ], tempJ-1] + p[tempJ];//  
                        int res2 = result[tempI,tempJ-1];//   
                        result[tempI, tempJ] = Math.Max(res1, res2);
                    }
                }      
            }
           
            return result[m, i];
        }
        public static void getList(int length,int m,int[] w) {
            int tempM = m;
            for (int tempI = length-1; tempI >= 1; tempI--) {
                if (result[tempM, tempI] > result[tempM, tempI - 1]) {
                    best.Add(tempI);
                    TotalWeight += w[tempI];
                    tempM -= w[tempI];
                }
            }
        }
    }
}