01BackPack

#include<iostream>
using namespace std;
const int num = 4; //物品数量
const int weight = 13; //背包承载量
int v[num + 1] = {0, 12, 11, 9, 8}; //物品价值
int w[num + 1] = {0, 8, 6, 4, 3};  //物品重量
int m[num + 1][weight + 1] = {0};
//m[i][j]:装前i个物品总重量不超过j的最大价值
int s[num + 1][weight + 1] = {0};
//s[i][j]:装前i个物品总重量不超过j转入物品的最大标号
int main(){
    for(int i = 1; i <= num; i++){
        for(int j = 1; j <= weight; j++){
            if( j >= w[i] && m[i-1][j-w[i]] + v[i] > m[i-1][j]){
                m[i][j] = m[i-1][j-w[i]] + v[i];
                s[i][j] = i;
            }
            else{
                m[i][j] = m[i-1][j];
                s[i][j] =  s[i-1][j];
            }
        }
    }
    cout<<m[num][weight]<<endl;
    return 0;
}