完全背包問題-動态規劃

• 題目描述

  設有N種物品，每種物品有一個重量及一個價值。但每種物品的數量是無限的，同時有一個背包，最大載重量為M，今從N種物品中選取若幹件(同一種物品可以多次選取)，使其重量的和小于等于M，而價值的和為最大。

• 輸入

  第一行：兩個整數，M(背包容量，M<=200)和N(物品數量，N<=30)；第2..N+1行：每行二個整數wi，vi，表示每個物品的重量和價值。

• 輸出

  僅一行，一個數，表示最大總價值。

• 樣例輸入

  10 4

  2 1

  3 3

  4 5

  7 9

• 樣例輸出

  max=12

• Analysis

  使用一個數組f[]，其中f[i]表示使用背包i的容量時可以得到的最大價值，f[M]即為解

• 源代碼

#include <iostream>
#include <cstdio> 
#include <algorithm> 

using namespace std;

int w[],v[],f[];
int M,N; 

int main()
{   
    scanf("%d%d",&M,&N);
    for(int i=;i<=N;i++)
        scanf("%d%d",&w[i],&[i]);
    for(int i=;i<=N;i++)
        for(int j=w[i];j<=M;j++)
            f[j]=max(f[j],f[j-w[i]]+v[i]); 
    printf("\nmax=%d\n",f[M]); 
    return ; 
}