알고리즘 학습 노트 의 기초 dp 의 (0 / 1) 가방 문제

0 / 1 가방 은 가장 전형 적 인 dp 문제 입 니 다.
가방 문제: 여러 개의 아 이 템 이 있 습 니 다. 무게 가 다 르 고 가치 가 다 르 며 용량 이 제 한 된 가방 을 선택 하여 가방 에 부 딪 히 는 아 이 템 을 선택 하고 가방 에 넣 는 아 이 템 의 총 가치 가 가장 큽 니 다.서로 다른 한정 조건 에 따라 가방 문 제 를 여러 가지 로 나 눌 수 있 는데 흔히 볼 수 있 는 것 은 다음 과 같은 두 가지 가 있다.
4. 567917. 모든 물품 을 나 눌 수 있다 면 일반 가방 문제 라 고 부 르 고 욕심 법 으로 최 적 화 를 구한다.예 를 들 어 뷔페 를 먹 을 때 식사량 이 일정한 상황 에서 어떻게 먹 어야 뱃속 의 가장 값 진 음식 을 먹 을 수 있 습 니까?가장 비 싼 음식 부터 먹고 가장 비 싼 것 을 먹고 두 번 째 비 싼 것 을 먹 는 것 이 욕심 이다.예 를 들 어 산타클로스 의 선물. - 산 타 클 라 우 스 기 프 트 OpenJBailian - 4110 크리스마스 가 왔 습 니 다. 도시 A 에서 산 타 할 아버 지 는 사탕 을 나 누 어 주 려 고 합 니 다. 지금 은 여러 상자 의 서로 다른 사탕 이 있 습 니 다. 각 상자 의 사탕 은 자신의 가치 와 무게 가 있 고 모든 상자 의 사탕 은 임의로 나 누 어 조합 해서 가 져 갈 수 있 습 니 다.산타클로스 의 루 돌 프 는 최대 일정 무게 의 사탕 만 받 을 수 있 는데, 산타클로스 가 가장 많은 가치 의 사탕 을 가 져 갈 수 있 는 지 물 어보 세 요.Input 첫 줄 은 두 부분 으로 구성 되 어 있 으 며, 각각 사탕 상자 의 정수 n (1 < = n < = 100), 루 돌 프 가 감당 할 수 있 는 최대 중량 의 정수 w (0 < w < 10000), 두 수 는 빈 칸 으로 나 뉜 다.나머지 n 줄 은 한 상자 의 사탕 에 대응 하고 두 부분 으로 구성 되 며 각각 한 상자 의 사탕 의 가치 정수 v 와 무게 정수 w 로 중간 에 빈 칸 으로 분리 된다.아웃 풋 은 산 타 할아버지 가 가 져 갈 수 있 는 사탕 의 최대 총 가 치 를 출력 해 1 자리 소 수 를 유지한다.줄 바 꿈 문자 로 출력 을 한 줄 로 끝 냅 니 다.Sample Input 4 15 100 4 412 8 266 7 591 2 Sample Output 1193.0

#include
#include
#include
using namespace std;

struct suger {
     
	int v,w;//v   ，w   
	double x;//x          
}record[101];

bool cmp(const suger& a, const suger& b ) {
     
	return a.x > b.x;
}//        ，          

int main()
{
     
	int n, W;
	scanf("%d %d", &n, &W);
	for (int i = 0; i < n; i++) {
     
		scanf("%d %d", &record[i].v, &record[i].w);
		record[i].x = record[i].v / record[i].w;
	}
	sort(record, record + n, cmp);
//	for (int i = 0; i < n; i++) {
     
//		printf("%d ", record[i].v);
//	}
	int sum = 0;
	double max = 0;
	for (int i = 0; i < n; i++) {
     
		sum += record[i].w;
		if (sum <= W) {
     
			max += record[i].v;
		}
		else if (sum > W) {
     
			max += ((W - sum + record[i].w) * record[i].x);
			break;
		}
	}
	printf("%.1f
", max);
}

4. 567917. 만약 에 모든 물체 가 분리 할 수 없 으 면 0 / 1 가방 문제 가 된다.여전히 뷔페 의 경우 이번 음식 은 1 인분 이 고 1 인분 은 다 먹 어야 한다.만약 가장 비 싼 것 이 너의 식사량 을 초과 한다 면 포기 할 수 밖 에 없다.이런 문 제 는 욕심 으로 최 적 화 를 구 할 수 없다
01 가방 문제 설명: a, b, c, d, e 의 다섯 가지 아 이 템 이 있 습 니 다. 그들 이 차지 하 는 공간 은 각각 2, 2, 6, 5, 4 입 니 다. 그들의 가 치 는 각각 6, 3, 5, 4, 6 입 니 다. 각 아 이 템 의 수량 은 하나 입 니 다. 지금 은 10 개의 가방 을 드 리 겠 습 니 다. 가방 에 담 긴 아 이 템 이 가장 큰 가 치 를 가지 게 하 는 방법 은 무엇 입 니까?i 호 아 이 템 을 넣 을 지 안 넣 을 지 고려: i 호 아 이 템 을 넣 을 때 f [i] [v] = f [i - 1] [v - w [i]] + p [i] 는 (p [i] 는 i 호 아 이 템 의 가 치 를 표시 함), i - 1 번 선택 후 선택 한 아 이 템 의 용량 이 v - w [i] 인 가방 에 넣 으 면 최대 가 치 는 f [i - 1] [v - w [i]] 를 얻 을 수 있 으 며, 현재 선택 한 i 호 아 이 템 의 가치 p [i] 는 f [i] [v] 이다.
2. i 호 아 이 템 을 넣 지 않 을 때 f [i] [j] = f [i - 1] [j].전 i - 1 차 선택 소득 의 가장 큰 가 치 를 나타 낸다.
그래서 우 리 는 01 가방 의 전달 공식 을 얻 을 수 있다. f [i] [v] = max {f [i - 1] [v], f [i - 1] [v - w [i]] + p [i]} 템 플 릿:

for(int i = 1; i <= n; i++)
        {
     
            for(j = w[i]; j <= V; j++)
                f[i][j] = max(f[i-1][j], f[i-1][j-v[i]]+w[i]);
        }

1 차원 배열 최적화:

for(int i=1;i<=n;i++)
{
     
    for(int c=V;c>=0;c--)
    {
     
        if(c>=v[i])
        f[c]=max(f[c],f[c-v[i]]+w[i]);
    }
}

예제: HDU 2602 Bone Collector
N 개의 사탕 의 무게 와 가 치 를 알 고 있 습 니 다. 우 리 는 주머니 가 하나 있 습 니 다. V 의 무 게 를 가장 많이 담 을 수 있 는 사탕 이 있 습 니 다. 주머니 에 얼마나 많은 사탕 을 넣 을 수 있 는 지 물 어보 세 요.
Input 이 입력 한 첫 번 째 줄 은 T 로 T 조 의 데 이 터 를 표시 합 니 다. 각 조 의 데 이 터 는 세 줄 로 구성 되 어 있 습 니 다. 첫 번 째 줄 은 두 개의 정수 N 과 V (N < = 1000, V < = 1000) 를 포함 합 니 다. N 은 사탕 의 개 수 를 표시 하고 V 는 주머니 의 적재량 을 표시 합 니 다. 두 번 째 줄 은 N 개의 정 수 를 포함 하여 각 사탕 의 가 치 를 표시 합 니 다. 세 번 째 줄 은 N 개의 정 수 를 포함 하여 각 사탕 의 무 게 를 표시 합 니 다.
출력 은 각 그룹의 데이터 에 대해 출력 주머니 에 최종 적 으로 사탕 의 가 치 를 넣 을 수 있 습 니 다. Sample Input 1 5 10 1 2 3 4 5 4 3 2 1 Sample Output 14 는 템 플 릿 을 직접 세트 하면 됩 니 다.

#include
#include
using namespace std;

struct Node {
     
	int val;
	int vol;
}node[1010];
int t, n, v;
int dp[1010][1010];

int ans()
{
     
	memset(dp, 0, sizeof(dp));
	for (int i = 1; i <= n; i++) {
     
		for (int j = 0; j <= v; j++) {
     
			if (node[i].vol > j)
				dp[i][j] = dp[i - 1][j];
			else
				dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - node[i].vol] + node[i].val);
		}
	}
	return dp[n][v];
}
int main()
{
     
	cin >> t;
	while (t--) {
     
		cin >> n >> v;
		for (int i = 1; i <= n; i++) cin >> node[i].val;
		for (int i = 1; i <= n; i++) cin >> node[i].vol;
		cout << ans() << endl;
	}
	return 0;
}

가방 문 제 는 완전 가방 과 다 중 가방 등 이 있 습 니 다.