중급편-가방 문제3(다중 가방)

전편에서 말한 완전배낭이란 모든 물품의 수량이 무한한 상황에서 최치를 선택하는 것을 말한다. 현재 다중배낭 문제를 제기하고 있다. 즉, 각 물품의 개수는 w[i]가 모두 유한하고 반드시 같지 않으며 모든 물품이 그 가치가 있다는 것이다. 이런 상황에서 최치를 구한다.
다중 배낭 문제의 특징은 데이터량이 많기 때문에 01배낭의 방법에 따라 dp[m][n]의 수조를 열거하면 반드시 시간을 초과할 수 있기 때문에 수조를 만들 때 dp[maxn](maxn은 데이터가 달성할 수 있는 최대치)를 개설한다.
그룹 dp[]을 모두 0으로 초기화하고 dp[0]을 1로 설정합니다.이중 순환 i를 이용하여 1에서 n까지 w[i]를 누비고 내부 순환 j는 v[i]부터 뒤로 누비며 dp[j-v[i]의 값이 진실(즉 가치 j-v[i]가 만족할 수 있음을 나타낸다)이고 dp[j]의 값이 가짜(가치 j가 만족하지 않았다는 뜻)라면 가치 j는 도달할 수 있다.왜 가능하다고 해요?가치 j에 도달할 수 있는지도 v[i]의 수량이 상한선에 도달하는지의 여부에 달려 있기 때문이다.어떻게 w[i]의 수량을 기록합니까?개수를 전문적으로 기록하는 수조num[maxn]을 개설하여 1층 순환에서 수조num[]를 0으로 초기화하고 dp[j-v[i]를 만족시키면 &!dp[j] & &num[j-v[i]num[j]=num[j-v[i]+1 가치 j가 대응하는 가치가 v[i]인 물품의 사용수는 가치가 j-v[i]인 토대에서 1을 더하는 것이 특히 관건입니다!그 다음에 제목의 뜻에 따라 어떤 쪽을 구하면 됩니다.
특별히 강조하다.다중 가방은 가방 문제의 마지막 편이지만 그 템플릿이 가장 잘 작동합니다. 거의 백 세트 백 중입니다!
템플릿:

for(int i=1;i<=n;i++)
    {
        memset(num,0,sizeof(num));
        for(int j=v[i];j<=maxn;j++)
        {
            if(dp[j-v[i]&&!dp[j]&&num[j-v[i]]

전례:http://acm.hdu.edu.cn/showproblem.php?pid=2191
중국어 문제는 못 알아보는 것이 없다.
사고방식 분석: 전형적인 다중 가방 문제는 1차원수 그룹 dp[]를 개설하면 차원 maxn이 최대 가치량이다. 이후에 상술한 사고방식에 따라 이중 순환하면 dp[maxn]에 대응하는 것이 살 수 있는 최대 상황이다.

#include 
#include 
#include 
#include 
using namespace std;

int main()
{
    int T,n,m;
    int v[105],w[105],num[105],dp[105];
    cin>>T;
    while(T--)
    {
        cin>>m>>n;
        for(int i=0;i>v[i]>>w[i]>>num[i];
        memset(dp,0,sizeof(dp));
        for(int i=0;i=v[i];k--)
                    dp[k]=max(dp[k],dp[k-v[i]]+w[i]);
        cout<

전례 2:http://poj.org/problem?id=1742
제목: n가지 가치의 동전은 종류마다 그 수량 w[i]가 있고 최대 가치량 m에 최대 가치량을 초과하지 않는 상황에서 얼마나 많은 가치를 모을 수 있는지 구한다.
분석: 이 문제는 바로 사고방식에 따라 틀을 씌우면 된다.

#include 
#include 
#include 
using namespace std;

int use[100001];
int n,m;
bool dp[100001];
int v[1001],num[1001];
int main() 
{
    while (scanf("%d %d", &n, &m) != EOF) 
    {
        if (n == 0 && m == 0) break;
        for (int i = 0; i < n; ++i)
            scanf("%d", a+i);
        for (int i = 0; i < n; ++i) 
            scanf("%d", num+i);
        int res = 0;
        memset(dp,false,sizeof(dp));
        dp[0] = true;
        for (int i = 0; i < n; ++i) 
        {
            memset(use,0,sizeof(use));
            for (int j = a[i]; j <= m; ++j) 
            {
                if (!dp[j] && dp[j-a[i]] && use[j-a[i]]