낙 곡 P1064 김 명의 예산 안

901 단어 낙 곡
제목 전송 문
제목 의 의미: 총 금액 m, 물품 총 수량 n.각 물품 은 한 번 만 살 수 있 으 며, 첨부 파일 을 사려 면 반드시 주 부품 을 사 야 한다.총 금액 의 최대 가 치 를 초과 하지 않도록 구하 다.
메 인 1 과 첨부 2, 3, 4 의 구 매 방법 은 12, 13, 123, 14, 124, 134, 1234 로 이 조합 들 을 하나의 전체 로 볼 수 있 고 매번 에 그 중에서 하나의 조합 을 선택 할 수 있다.01 가방 + 조별 가방 의 문제 입 니 다.
알고리즘 의 시간 복잡 도 는:
다음은 코드:
#include
#include
using namespace std;
int m,n;
int f[40000];
vector>item[65];
int main(){
	cin>>m>>n;
	for(int i=1;i<=n;i++){
		int w,v,q;
		cin>>w>>v>>q;
		if(q==0){
			item[i].push_back({w,w*v});
		}else{
			int sz=item[q].size();
			for(int j=0;j=1;j--)
			for(int k=0;k=item[i][k].first){
					f[j]=max(f[j],f[j-item[i][k].first]+item[i][k].second);
				}
	}
	cout<

 

좋은 웹페이지 즐겨찾기