hdoj 2191 다 중 가방 입문 문제

제목 링크:http://acm.hdu.edu.cn/showproblem.php?pid=2191
이 문 제 는 벌 거 벗 은 멀 티 백 입문 문제 다.순 전 히 가방 9 강 에 대한 자신의 이 해 를 측정 하 는 데 쓰 인 다.
결국 WA 는 여러 그룹의 데이터 순환 문 구 를 잊 어 버 렸 다.역시 너무 오 랜 만 에 써 서 갈수 록 엉망이다.
이곳 에서 사용 하 는 첫 번 째 방법 은 01 가방 문제 로 바 뀌 었 고 최적화 되 지 않 았 다.
상태 전이 방정식 은 F [i, v] = max {F [i - 1, v - k * 8727 ° C i] + k * 8727 ° W i | 0 ≤ k ≤ M i}
그리고 우 리 는 여전히 1 차원 배열 로 전환 하여 구 해 를 할 수 있다.
여기에 이 방법의 코드 를 첨부 합 니 다:
4. 567913. 그리고 한 가지 방법 은 2 진법 으로 전환 하 는 방법 이다.배낭 9 강 에서 이렇게 말 했다.
여전히 이 진 사상 을 고려 하고 있 습 니 다. 우 리 는 제 i 종 물품 을 몇 가지 물품 으로 바 꾸 어 원래 문제 에서 제 i 종 물품 이 취 할 수 있 는 모든 전략 인 0... M i 건 을 취하 면 모두 몇 가지 물건 을 대체 한 후의 물품 과 등가 할 수 있 습 니 다.또한 M i 를 초과 하 는 정책 은 나타 나 지 않 습 니 다.방법 은 i 번 째 아 이 템 을 01 가방 에 있 는 아 이 템 으로 나 누 는데 그 중에서 모든 아 이 템 은 하나의 계수 가 있다.이 물품 의 비용 과 가 치 는 모두 원래 의 비용 과 가 치 를 이 계수 에 곱 한 것 이다.이 계 수 를 각각 1, 2 ^ 2, 2 ^ 3,... 2 k - 1, M - i - 2 k + 1 로 하고 k 는 M - 2 k + 1 > 0 을 만족 시 키 는 최대 정수 이다.예 를 들 어 만약 에 M i 가 13 이면 해당 하 는 k = 3 이 고 이런 최대 13 개 를 취 하 는 물품 은 계수 가 각각 1, 2, 4, 6 인 네 개의 물품 으로 나 누 어야 한다.나 누 어 진 이 몇 가지 물품 의 계수 와 M i 는 M i 보다 많은 i 가지 물품 을 취 할 수 없다 는 것 을 나타 낸다.또한 이런 방법 은 0... M i 간 의 모든 정수 에 대해 몇 개의 계수 와 표 시 를 사용 할 수 있다 는 것 을 보증 할 수 있다.여기 서 알고리즘 의 정확성 을 증명 하 는 것 은 0... 2 k - 1 과 2 k... M. i 두 단락 으로 나 누 어 토론 할 수 있 으 니 독자 스스로 생각 하고 시도 해 보시 기 바 랍 니 다.
의사 코드 는 다음 과 같 습 니 다:
def MultiplePack( F , C , W , M ) if C · M ≥ V CompletePack( F , C , W ) return k := 1 while k < M ZeroOnePack( kC , kW ) M := M − k k := 2k ZeroOnePack( C · M , W · M )
생각해 보 니 위조 코드 의 분할 방식 은 앞의 것 과 같 지 않 습 니 다. 위조 코드 에 서 는 가방 의 분할 을 1, 2 ^ 2, 2 ^ 3,........................................................   또한 k 는 m - 2 ^ k > 0 을 만족 시 키 는 최대 정수 입 니 다.
이렇게 몇 개 를 가 져 와 도 모든 방식 을 표시 할 수 있 기 때문에 똑 같 을 것 이다.
그래서 이 방법 을 실현 시 켰 다.
코드 는 다음 과 같 습 니 다:

#include<iostream>
#include<cstring>
using namespace std;
int c[110];
int w[110];
int m[110];
int dp[110];
int max(int a,int b)
{
	return (a>b)?a:b;
}
int main ()
{
	int t,n,V;
	cin >> t;
	while(t--)
	{
		memset(dp,0,sizeof(dp));		
		cin >> V >> n;
		for(int i = 1;i <= n;i++)
		cin >> c[i] >> w[i] >> m[i];
		for(int i = 1;i <= n;i++)
		{
			for(int j = V;j >= c[i];j--)
			{
				for(int k = 1;k <= m[i] && k*c[i] <= j;k++)  //   k         ，          
					dp[j] = max(dp[j],dp[j-k*c[i]]+k*w[i]);
			}
		}
		cout << dp[V] << endl;
	}
	return 0;
}