【 알고리즘 노트 】 가방 DP ④ 2 차원 비용 가방 (2 차원 01 가방)

1. 간단 한 템 플 릿 예제 (로 곡 에서 선택)
속담 에 이 르 기 를 "지피지기 하면 백 번 싸워 도 위 태 롭 지 않다" 고 했다.L 국 의 지휘관 이 간첩 을 I 국 으로 보 내 려 하 자 선발 작업 이 당신 에 게 떨 어 졌 습 니 다.
당신 은 지금 N 명의 사람 이 있 습 니 다. 모든 사람 은 이런 데 이 터 를 가지 고 있 습 니 다. A (자 료 를 얼마나 얻 을 수 있 습 니까?), B (위장 능력 이 얼마나 떨 어 지 는 지), C (월급 이 얼마나 필요 합 니까?적의 스파이 탐지 능력 이 M (즉, 가 는 모든 사람의 B 와 M 보다 작 아야 함) 이 고 수중 에 X 원 이 있 는 것 으로 알려 져 있 습 니 다. 자 료 를 얼마나 받 을 수 있 습 니까? \ # \ #p1910
분명히 여기 에는 두 개의 가방 이 있 는데 B 는 첫 번 째 가방 B, C 는 두 번 째 가방 이 고 A 는 가치 이 며 모든 물품 에 도 두 가지 속성 이 있 습 니 다. 그러면 어떻게 해결 해 야 합 니까?
01 가방 은 이렇게 적 혀 있다: f [j] = max (f [j], f [j - v [i]] + w [i])
그러면 우 리 는 1 차원 만 추가 하면 된다. f [i] [j] = max (f [i] [j], f [i - v1 [i]] [j - v2 [i]]] + w [i])
그럼 코드 를 드 리 겠 습 니 다.
방법 은 01 가방 과 유사 합 니 다:

#include
using namespace std;
int n,m,x;
int a[10000]={};
int b[10000]={};
int c[10000]={};
int f[5000][5000]={};
int main()
{
	cin>>n>>m>>x;
	for (int i=1;i<=n;i++)
	    cin>>a[i]>>b[i]>>c[i];
	for (int i=1;i<=n;i++)
	    for (int j=m;j>=b[i];j--)
	        for (int k=x;k>=c[i];k--)
	            f[j][k]=max(f[j][k],f[j-b[i]][k-c[i]]+a[i]);
	cout<

2. 최소 2 차원 비용 가방 구하 기
잠수부 들 은 잠수 하기 위해 특별한 장 비 를 사용 해 야 한다.그 는 두 가지 기 체 를 가 진 실린더 가 있다. 하 나 는 산소 이 고 하 나 는 질소 이다.잠수부 가 잠수 하 는 깊이 는 각종 수량의 산소 와 질 소 를 필요 로 한다.잠수부 에 게 는 일 정량의 실린더 가 있다.모든 실린더 에는 무게 와 가스 용량 이 있다.잠수부 가 그의 일 을 완성 하기 위해 서 는 특정 수량의 산소 와 질소 가 필요 하 다.그 가 일 을 완성 하 는데 필요 한 실린더 의 총 중량 의 최저 한 도 는 얼마 입 니까?예 를 들 어 잠수부 에는 5 개의 실린더 가 있다.각 줄 의 세 가지 숫자 는 산소, 질소 (리터) 량 과 실린더 의 무게 이다.
　　3 36 120
　　10 25 129
　　5 50 250
　　1 45 130
　　4 20 119
잠수부 가 5 리터 의 산소 와 60 리터 의 질 소 를 필요 로 한다 면 총 무 게 는 최소 249 (1, 2 또는 4, 5 호 실린더) 이다.당신 의 임 무 는 잠수부 가 그의 일 을 완성 하기 위해 필요 한 실린더 의 무 게 를 계산 하 는 것 입 니 다. 
분명히 이 문제 의 사고방식 은 이전의 문제 와 같다.
상태의 의미 에 있어 차이 가 있다. f [i] [j] 는 i 와 같은 산소 와 j 와 같은 질소 가스 의 최소 치 를 나타 낸다.
우리 가 i 를 매 거 하 러 갈 때 j 와 k 매 거 와 i 로 같은 가방 의 다른 부피 에 있 습 니 다. 마지막 으로 최소 치 를 구하 면 됩 니 다.
초기 화: f [0] [0] = 0

#include
using namespace std;
int T,A,n,ans=999999999;
int w[5000]={};
int t[5000]={};
int a[5000]={};
int f[500][500]={};//f[i][j]      i        j        
int main()
{
	memset(f,100,sizeof(f));
	f[0][0]=0;//    
	cin>>T>>A>>n; 
	for (int i=1;i<=n;i++)
	    cin>>t[i]>>a[i]>>w[i];
	for (int i=1;i<=n;i++)
	    for (int j=T;j>=0;j--)//    i              
		    for (int k=A;k>=0;k--)//      
			{
				int Y=j+t[i];//            
				int D=k+a[i]; //     
				Y=min(Y,T);
				D=min(D,A);//            f[n][m]  ，        f[n][m]
				f[Y][D]=min(f[Y][D],f[j][k]+w[i]);//   i            
			}
	cout<<f[T][A];
	return 0;
}