FZU-2214-Knapsack 문제[01 가방]

**

Knapsack problem

** Problem Description
Given a set of n items, each with a weight w[i] and a value v[i], determine a way to choose the items into a knapsack so that the total weight is less than or equal to a given limit B and the total value is as large as possible. Find the maximum total value. (Note that each item can be only chosen once).
Input The first line contains the integer T indicating to the number of test cases.
For each test case, the first line contains the integers n and B.
Following n lines provide the information of each item.
The i-th line contains the weight w[i] and the value v[i] of the i-th item respectively.
1 <= number of test cases <= 100
1 <= n <= 500
1 <= B, w[i] <= 1000000000
1 <= v[1]+v[2]+…+v[n] <= 5000
All the inputs are integers.
Output For each test case, output the maximum value.
Sample Input 1 5 15 12 4 2 2 1 1 4 10 1 2
Sample Output 15
제목 링크: FZU-2214
제목 대의: n개 아이템, w 용량이 가장 가치가 높습니다.가방
제목 사고방식: dp[i][j]는 i번째 아이템까지 가치가 j의 용량 최소치임을 나타낸다.
다음은 코드입니다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include<map>
using namespace std;
long long dp[505][5005]; //w  
int v[5005];
long long w[5005];
#define INF 1000000707
int main(){
    int t;
    cin >> t;                       
    while( t-- ){
        int n,b;
        cin >> n >> b;
        memset(dp,0,sizeof(dp));
        int sum = 0;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> w[i] >> v[i];
            sum += v[i];
        }
        for (int i = 0; i <= n; i++)
        {
            for( int j=0 ; j<=sum ; j++ )
            {
                    dp[i][j] = INF;
            }
        }
        for (int i = 0; i <= n; i++) dp[i][0] = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j < v[i]; j++)
            {
                dp[i][j] = dp[i - 1][j];
            }
            for (int j = v[i]; j <= sum ; j++ )
            {
                dp[i][j] = dp[i - 1][j];
                if (dp[i - 1][j - v[i]] == INF) continue;
                dp[i][j] = min(dp[i][j],dp[i - 1][j - v[i]] + w[i]);
                if (dp[i][j] <= b)
                {
                    ans = max(ans,j);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}

스크롤 배열:

#include <iostream>
#include <cmath>
#include <cstring>
#include <string>
#include <cstdio>
#include <vector>
#include <algorithm>
#include<map>
using namespace std;
long long dp[5005]; //w  
int v[505];
long long w[505];
#define INF 1000000707
int main(){
    int t;
    cin >> t;
    while( t-- ){
        int n,b;
        cin >> n >> b;
        memset(dp,0,sizeof(dp));
        int sum = 0;
        int ans = 0;
        for (int i = 1; i <= n; i++)
        {
            cin >> w[i] >> v[i];
            sum += v[i];
        }
        for( int j=0 ; j<=sum ; j++ )
        {
            dp[j] = INF;
        }
        dp[0] = 0;
     // for (int i = 0; i <= n; i++) dp[i][0] = 0;

        for (int i = 1; i <= n; i++)
        {
            for (int j = sum; j >= v[i] ; j--)
            {
                if (dp[j - v[i]] == INF) continue;
                dp[j] = min(dp[j],dp[j - v[i]] + w[i]);
                if (dp[j] <= b)
                {
                    ans = max(ans,j);
                }
            }
        }
        cout << ans << endl;
    }
    return 0;
}