배낭 문제 소결
레이 블: 아래 n 은 물품 건수 이 고 c [i] 는 i 번 째 물품 의 소모 (부피), V 는 가방 용량 이 며 a [i] 는 i 번 째 물품 의 가치 dp [] 배열 이 보관 하 는 것 이 가장 좋 은 것 임 을 나타 낸다.
가방
가장 간단 한 가방 으로 아 이 템 마다 선택 하거나 선택 하지 않 습 니 다.
for(int i = 1; i <= n; ++i){
for(int j = V; j >= c[i]; --j){
dp[j] = max(dp[j],dp[j-c[i]]+a[i]);
}
}완전 가방
아 이 템 당 무한 회 선택 가능
for(int i = 1; i <= n; ++i){
for(int j = c[i]; j <= V; ++j){
dp[j] = max(dp[j],dp[j-c[i]] + a[i];
}
}주의: 초기 화 방면 의 세부 사항, 만약 에 가방 을 적당 하 게 채 워 야 한다 면 초기 화 할 때 dp [0] 을 제외 하고 다른 dp [1. V] 는 모두 - 표시 (가장 큰 해 를 구 하 는 것 이 고 가장 작은 해 를 구 하 는 것 이 라면 표시) 로 설정 합 니 다. 등 을 가득 채 워 야 한 다 는 요구 가 아니 라 가격 이 최대한 비 싸 기 를 원한 다 면 초기 화 할 때 f [0. V] 를 모두 0 으로 설정 해 야 한다.
3. 다 중 가방
각 아 이 템 선택 가능 횟수 제한 각 아 이 템 의 개 수 를 count [i] 로 설정 하기;
O(V*Σlog count [i]) 쓰기 (바 이 너 리 최적화)
for(int i = 1; i <= n; ++i){
int k;
for(k = 1; k*2 < count[i] + 1; k *= 2){
for(int j = V; j >= k*c[i] ; --j){
dp[j] = max(dp[j],dp[j-k*c[i]] + k*a[i]);
}
}
k = count[i] + 1 - k;
for(int j = V; j >= k*c[i]; --j){
dp[j] = max(dp[j],dp[j-k*c[i]] + k*a[i]);
}
}O (VN) 의 표기 법
/ * 이 방법 은 최대 치 를 구 할 수 있 는 지 없 는 지 는 확실 하지 않 지만 1 - V 내 가방 을 가득 채 울 수 있 는 지 판단 할 수 있 습 니 다 * /
----------------------------------------------------------------------
int used[MAXN];
for(int i = 1; i <= N; ++i){
memset(used,0,sizeof(used));
for(int j = c[i]; j <= V; ++j){
if(used[j-c[i]] < count[i] && dp[j] < dp[j-c[i]] + a[i]){
dp[j] = dp[j-c[i]] + a[i];
used[j] = used[j-c[i]] + 1;
}
}
} // ， ， ----------------------------------------------------------------------
현재 dp [i] 용량 이 i 인 가방 이 위 에 있 는 01 가방 과 완전 가방, 위 에 있 는 O (V *Σlog count [i]) 의 표기 법 도 이런 변 화 를 할 수 있다.
memset(dp,false,sizeof(dp));
dp[0] = true;
for(int i = 1; i <= N; ++i){
memset(used,0,sizeof(used));
for(int j = c[i]; j <= V; ++j){ // （ ），
if(!dp[j] && dp[j-c[i]] && used[j-c[i]] < count[i]){ // !dp[j]
dp[j] = true;
used[j] = used[j-c[i]] + 1;
}
}
}혼합 가방
상기 세 가지 가방 의 혼합, 어떤 아 이 템 은 한 번 만 찾 을 수 있 고, 어떤 아 이 템 은 무한 회 찾 을 수 있 으 며, 어떤 아 이 템 은 유한 회 찾 을 수 있 습 니 다.
알고리즘 위조 코드:
for i=1..n
if 제 i 아 이 템 01 가방
for j=V...c[i]
dp[j]=max(); //가방 코드
else if 제 i 아 이 템 은 완전 가방
for j=c[i]...V
dp[j]=max(); //위 와 완전 가방.
else if 제 i 아 이 템 은 멀 티 백 팩
Multiple Pack (c [i], a [i], count [i]) / / 같은 다 중 가방
5. 2 차원 비용 의 가방
질문: 모든 물품 은 각자 의 부피 v [i] 와 무게 w [i] 가 있 습 니 다. 가방 하나 에 가장 많이 담 을 수 있 는 부 피 는 V 이 고 가장 많이 담 을 수 있 는 무 게 는 W 입 니 다. 가장 많이 담 을 수 있 는 가 치 를 물 어보 세 요.두 가지 속성 이 제 한 된 가방 문제 입 니 다.그 다음 에 일반적인 01 가방 문제 에 개수 제한, 즉 최대 K 개의 아 이 템 을 가 져 가 는 것 도 각 아 이 템 의 개수 소모 가 1 이 고 가방 에 용량 이 K 인 속성 을 추가 하 는 것 도 2 차원 비용 가방 으로 이해 할 수 있다.2 차원 비용 의 가방 은 dp 배열 에 1 차원 만 추가 하면 됩 니 다.
01 가방 을 예 로 들 면:
for i=1...n
for j=V..v[i]; //완전 가방 이면 for j = v [i].. V for k=w[i]..W;
for k=W..w[i];
dp[j][k] = max(dp[j][k],dp[j-v[i]][k-w[i]] + a[i]);
질문
n 개의 아 이 템 을 여러 조로 나 누 어 각 조 에서 한 개의 아 이 템 만 선택 할 수 있 고 얻 을 수 있 는 최대 가 치 를 물 어 볼 수 있 습 니 다.
for 모든 그룹 k
for v=V..0
for 모든 i 는 그룹 k 에 속 합 니 다.
dp[v]=max{dp[v],dp[v-c[i]]+a[i]}
7. 의존 하 는 가방 문제
한 가지 아 이 템 을 구 매 하려 면 다른 아 이 템 을 먼저 구 매해 야 합 니 다.이것 이 바로 의존 관계 가 있 는 가방 문제 입 니 다. 가방 9 강 에서 분명히 말 했 으 니 더 이상 말 하지 않 겠 습 니 다.
다음 두 부분 은 잠시 내 려 놓 겠 습 니 다.나중에 구체 적 인 문제 에 부 딪 혔 을 때 다시 보충 하 다.
8. 일반화 물품 의 가방
9. 가방 질문 법의 변화
다음은 비교적 고전적 인 문제 몇 가 지 를 말씀 드 리 겠 습 니 다. 01 가방 은 완전히 가방 은 말 하지 않 겠 습 니 다. 혼합 가방 도 말 할 필요 가 없습니다.
1. [POJ 1014] [TOJ 1034] [HDU 1059] [ZOJ 1419] Dividing - 다 중 가방 문제
보통 몇 개의 OJ 에서 동시에 등장 하고 오랫동안 쇠퇴 하지 않 는 문 제 는 모두 전형 적 인 문제 이다. 예 를 들 어 이 문 제 는 다 중 가방 에 관 한 문제 이다.
[제목 대의] 6 가지 가 치 는 각각 1, 2, 3, 4, 5, 6 의 돌 로 각 돌의 수 를 알려 주 고 이 돌 들 을 가치 가 같은 두 더미 로 나 눌 수 있 는 지 물 어보 자.
[해석] 전형 적 인 다 중 가방 문제, a [] 배열 은 1, 2, 3, 4, 5, 6 입 니 다. count 배열 문 제 를 드 리 겠 습 니 다. 어떻게 하 시 겠 습 니까?위 에서 언급 한 것 은 dp [i] 를 설치 하면 용량 이 i 인 가방 이 물체 에 가득 채 울 수 있 는 지 를 나타 낸다.dp [sum / 2] = 1 이면 두 무더기 (sum 은 모든 돌의 총 가치) 로 나 눌 수 있 고 위의 템 플 릿 을 직접 사용 하면 됩 니 다.
#include <cstdio>
#include <cstring>
using namespace std;
int a[10];
int dp[120100];
int main(){
int cas = 0;
while( ++ cas ){
int sum = 0;
for(int i = 1; i <= 6; ++i){
scanf("%d",&a[i]);
sum += a[i]*i;
}
if(sum == 0)break;
memset(dp,0,sizeof(dp));
printf("Collection #%d:
",cas);
if(sum % 2 == 1){
puts("Can't be divided.");
puts("");
continue;
}
dp[0] = 1;
//O（NV）
int dpt[120000];
for(int i = 1; i <= 6; ++i){
memset(dpt,0,sizeof(dpt));
for(int j = i; j <= sum/2; ++j){
if (!dp[j] && dp[j-i]&& dpt[j-i] < a[i]) {
dpt[j] = dpt[j-i] + 1;
dp[j] = 1;
}
}
}
/*
//
for(int i = 1;i <= 6;++i){
int k;
for(k = 1;k*2 < a[i]+1;k *= 2)
for(int v = sum/2;v >= k*i;--v)
if(dp[v-k*i])
dp[v]=true;
k = a[i]+1-k;
for(int v = sum/2;v > k*i;--v)
if([v-k*i])
dp[v] = true;
}
*/
if(dp[sum/2]){
puts("Can be divided.");
}
else {puts("Can't be divided.");};
puts("");
}
return 0;
}2. [TOJ 3540] Consumer 의존 관계 가 있 는 가방
【 제목 대 의 】 여러 조 의 아 이 템 을 주 고 각 조 의 아 이 템 은 하나의 상자 (상자 자체 에 도 cost 가 있 음) 가 있 습 니 다. 그 다음 에 아 이 템 의 cost 와 value 입 니 다. 어떤 아 이 템 을 사려 면 반드시 이 아 이 템 을 담 은 상 자 를 사 야 합 니 다. 일정한 돈 을 주 고 얻 을 수 있 는 최대 가 치 를 물 어 봐 야 합 니 다.
[문제 해석] 가방 9 강 6 강 과 7 강 내용 을 참조 하여 이 문 제 를 해결 할 수 있 습 니 다.
비교적 간단 한 표기 법 이 있 습 니 다. 가방 을 두 번 만 쓰 면 됩 니 다.
#include<iostream>
using namespace std;
const int MAXN = 100000;
int main()
{
int n,total,boxcost,goodnum,cost,value,i,j,t;
int dpbox[MAXN],dptotal[MAXN];
while(scanf("%d%d",&n,&total) != EOF)
{
memset(dptotal,0,sizeof(dptotal));
for(i = 0; i < n; i++)
{
scanf("%d%d",&boxcost,&goodnum);
memcpy(dpbox,dptotal,sizeof(dptotal));
for(j = 0; j < goodnum; j++)
{
scanf("%d%d",&cost,&value);
for(t = total - boxcost; t >= cost; t--)
{
if(dpbox[t] < dpbox[t - cost] + value)
dpbox[t] = dpbox[t-cost] + value;
}
}
for(t = total; t >= boxcost; t--)
if(dptotal[t] < dpbox[t-boxcost])
dptotal[t] = dpbox[t-boxcost];
}
printf("%d
",dptotal[total]);
}
return 0;
}3. [TOJ 3645] 당신 은 바 쁜
이 문 제 는 다 교 연합 경기 에서 유래 한 것 으로, 비교적 어 려 운 배낭 종합 문제 이다.
【 제목 대 의 】 한 사람 이 T 분 에 일 을 하 는데 모두 n 조 가 일 을 한다. 각 조 는 몇 가지 일 을 한다. 모든 업무 에 소모 되 는 시간 과 얻 은 즐거움 치 는 이미 알 고 있다. 각 조 는 하나의 표지 위치 가 있 고 표지 위 치 는 0 이면 이 조 에서 적어도 똑 같은 작업 을 선택해 야 한다. 표지 위 치 는 1 이면 이 조 에서 한 가지 업무 가 선택 되 고 표지 위 치 는 2 이 며 제한 이 없다.
[분석] 표지 의 위치 가 2 인 작업 팀 에 대해 제한 조건 이 없 기 때문에 모든 작업 을 할 수 있 고 하지 않 을 수 있 습 니 다. 즉, 간단 한 01 가방 으로 처리 할 수 있 습 니 다.표지 위 치 를 1 로 하 는 작업 팀 에 대해 서 는 기껏해야 하나의 작업 을 선택 하기 때문에 이번 작업 은 dp 배열 에 대해 최 적 화 된 값 을 선택 하여 한 번 만 업데이트 하면 된다.적어도 하 나 를 선택 한 작업 팀 에 대해 서 는 아직 이해 가 되 지 않 습 니 다. 다른 사람의 코드 만 보고 쓴 것 입 니 다. 그리고 여러분 들 은 많은 생각 을 모 아 댓 글 을 남 길 수 있 습 니 다. 나중에 이해 가 잘 되면 보충 하 겠 습 니 다.
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <queue>
#include <vector>
#include <map>
using namespace std;
const int maxt = 100 + 10;
int dp[maxt];
int td[maxt], n, m, t;
void dp0() { //
memcpy (td, dp, sizeof(td));
memset (dp, -1, sizeof(dp));
for (int i = 0, a, b; i < m; ++i) {
scanf ("%d%d", &a, &b);
for (int j = t; j >= a; --j) {// ？？
if (dp[j-a] != -1) {
dp[j] = max(dp[j], dp[j-a] + b);
}
if (td[j-a] != -1) {
dp[j] = max(dp[j], td[j-a] + b);
}
}
}
}
void dp1() { // , dp ，
memcpy(td, dp, sizeof(td));
for (int i = 0, a, b; i < m; ++i) {
scanf ("%d%d", &a, &b);
for (int j = t; j >= a; --j) {
if (td[j-a] != -1) {
dp[j] = max(dp[j], td[j-a] + b);
}
}
}
}
void dp2() { // ，01 ，
for (int i = 0, a, b; i < m; ++i) {
scanf ("%d%d", &a, &b);
for (int j = t; j >= a; --j) {
if (dp[j-a] != -1) {
dp[j] = max(dp[j], dp[j-a] + b);
}
}
}
}
void init() {
memset (dp, -1, sizeof(dp));
dp[0] = 0;
for (int i = 0, s; i < n; ++i) {
scanf ("%d%d", &m, &s);
if (s == 0) dp0();
else if (s == 1) dp1();
else if (s == 2) dp2();
}
}
void solve() {
int ans = -1;
for (int i = 0; i <= t; ++i)
ans = max(ans, dp[i]);
printf ("%d
", ans);
}
int main() {
//freopen("ar.txt","r",stdin);
while (scanf ("%d%d", &n, &t) != EOF) {
init();
solve();
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
Docker를 사용한 React 및 .NET Core 6.0 샘플 프로젝트 - 1부이 기사에서는 Entity Framework Core Code First 접근 방식을 사용하는 ASP.NET Core 6.0 WEP API의 CRUD(만들기, 읽기, 업데이트 및 삭제) 작업에 대해 설명합니다. 웹 ...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.
좋은 웹페이지 즐겨찾기
