완전 가방 입문 문제. [죽을 만큼 쉬운데...]

성명: 이 문제들은 대부분 판자 문제이고, HDU가 많으며, 신출내기 문제들은 모두 문제이며, 문제는 붙이지 않고, 직접 링크를 누르면 된다.

1. HDU- 1114 - Piggy-Bank

제목: 저금통 하나, 처음에 부피와 모두 담을 수 있는 부피를 주고 n개의 동전을 준다. 그에 상응하는 가치와 부피를 준다. 가득 채우면 최소한 얼마를 담을 수 있느냐고 묻는다. 동전은 무한 분석할 수 있다. 완전 배낭판 문제, 코드를 직접 볼 수 있다.

참조 코드

#include
using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int v[N],w[N],dp[N],s,e;
    ios_base::sync_with_stdio(0);
    int T;cin>>T;
    while(T--){
        int n;cin>>s>>e>>n;
        for(int i = 0;i < N;i++)dp[i] = INF;
        dp[0] = 0;
        for(int i = 0;i < n;i++){
            cin>>v[i]>>w[i];
        }
        for(int i = 0;i < n;i++){
            for(int j = w[i];j <= e-s;j++){
                dp[j] = min(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        if(dp[e-s] == INF)puts("This is impossible.");
        else printf("The minimum amount of money in the piggy-bank is %d.
",dp[e-s]);
    }
    return 0;
}

2. HDU - 1248 - 얼음의 왕좌

제목: N원짜리 지폐 하나만 드릴게요. 최소한 얼마를 낭비해 달라고 부탁하면 세 가지 물건을 살 수 있어요. 가격은 각각 150200350이에요. 한 개당 무한 분석할 수 있어요. 이것도 비교적 정확한 판자문제예요. 코드를 직접 보세요.

#include

using namespace std;

const int N = 1e5 + 10, INF = 0x3f3f3f3f;

int dp[N],a[5];
int main(){
    ios_base::sync_with_stdio(0);
    int T;cin>>T;
    a[0] = 150;a[1] = 200;a[2] = 350;
    while(T--){
        int n;cin>>n;
        for(int i = 0;i < N;i++)dp[i] = 0;
        for(int i = 0;i < 3;i++){
            for(int j = a[i];j <= n;j++){
                dp[j] = max(dp[j],dp[j-a[i]]+a[i]);
            }
        }
        cout<return 0;
}

3. HDU - 4508 - 추추 시리즈 이야기 - 다이어트

제목: 나체 완전 가방, 중국어로 직접 보면 OK oAo 참조 코드:

#include
using namespace std;

const int N = 1e5 + 10;
int dp[N],v[N],w[N];
int main(){
    ios_base::sync_with_stdio(0);
    int n;
    while(cin>>n){
        memset(dp,0,sizeof(dp));
        for(int i = 0;i < n;i++)cin>>v[i]>>w[i];
        int V;cin>>V;
        for(int i = 0;i < n;i++){
            for(int j = w[i];j <= V;j++){
                dp[j] = max(dp[j],dp[j-w[i]]+v[i]);
            }
        }
        cout<return 0;
}

업데이트 대기...