[맞음] 백준 12865 평범한 배낭 c++ // dp는 경우의수로 해결, ox dp

https://www.acmicpc.net/problem/12865

12865번: 평범한 배낭

1. dp는 if(dp[i][j]=~~~)

else dp[i][j]=~~~ 

형태로 해결하라

 

2. 전체코드

#include <bits/stdc++.h>
using namespace std;

int n, k,ret;
int d[104][100000+4]; // i번째 물건까지 왔을때 최대가치, 제한무개 j
int weight[100 + 4];
int value[100 + 4];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	for (int i = 1; i <= n; ++i) {
		int w, v;
		cin >> w >> v;
		weight[i] = w;
		value[i] = v;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= k; ++j) {
			//i번째 물건을 넣을수 없는경우
			if (j < weight[i]) {
				d[i][j] = d[i - 1][j]; 
				//기존에 탐색했던 물건들을 이용해서 무게 j를 만든 최대가치와 동일
			}
			//i번째 물건을 넣을수 있는경우
			else {
				//기존에 탐색했던 물건들로 무게j를 만드는경우
				//기존에 탐색했던 물건들로 무게 j-weight[i]를 만들고, 넣기
				//중 가치가큰값
				d[i][j] = max(d[i - 1][j], d[i - 1][j - weight[i]] + value[i]);
			}
				
		}
	}
	cout << d[n][k];
	
	return 0;
}

 

* 2회독(25.3.18.)

• 넣는경우, 안넣는경우 이진트리 dp

#include<bits/stdc++.h>
using namespace std; 

typedef long long ll;

int n,k;
vector<pair<int,int>> v; //무게, 가격
ll dp[104][100000+4]; //idx, 남은무게 : 그때 가치 최대값

ll dfs(int idx, int weight) {
   if(weight < 0 ) {
      return -987654321;
   }
   if(idx==n) {
      return 0;
   }

   ll & ret = dp[idx][weight];
   if(ret!=-1) {
      return ret;
   }

   ret=0; //리프노드 시작 리턴값
   ret=max(ret,dfs(idx+1,weight-v[idx].first)+v[idx].second); //담음
   ret=max(ret,dfs(idx+1,weight)); //안담음
   return ret;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin.tie(0); cout.tie(0);

   memset(dp,-1,sizeof(dp));
   cin>>n>>k;
   for(int i=0;i<n;++i) {
      int w,vv;
      cin>>w>>vv;
      v.push_back({w,vv});
   }
   cout<<dfs(0,k);
}

 

* 큰돌풀이

• 1개갯수제한은? 우측부터 표 dp