01背包

#include <iostream>
#include <vector>
using namespace std;

class Solution
{
public:
	void solve()
	{
		int W, N;
		cin >> W >> N;
		vector<vector<int>> dp(N + 1, vector<int>(W + 1, 0));
		vector<int> wt(N + 1);
		wt[0] = 0;
		vector<int> val(N + 1);
		val[0] = 0;

		for (int i = 1; i <= N; ++i) //item
		{
			cin >> wt[i] >> val[i];
		}

		for (int i = 1; i <= N; ++i)
		{
			for (int w = 1; w <= W; ++w)
			{
				if (w - wt[i] < 0)
				{
					dp[i][w] = dp[i - 1][w];
				}
				else
				{
					dp[i][w] = max(dp[i - 1][w], dp[i - 1][w - wt[i]] + val[i]);
				}
			}
		}

		cout << dp[N][W] << "\n";
	}
};

Solution s;

int main() {
	s.solve();
}

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n,c;
    cin>>n>>c;
    int w[n], v[n];
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    int dp[c+1];
    memset(dp,0,sizeof(dp));
    for(int i=0;i<n;i++)
        for(int j=c;j>=w[i];j--)
            dp[j] = max(dp[j], dp[j-w[i]]+v[i]);
    cout<<dp[c]<<endl;
    return 0;
}

import sys
input = []
for line in sys.stdin:
    input.append(line.strip().split())

volumn = int(input[0][0])
weights = [int(x[0]) for x in input[1:]]
values = [int(x[1]) for x in input[1:]]
num_items = len(weights)

dp = [[0 for _ in range(volumn+1)] for _ in range(num_items)]
for i in range(0, weights[-1]):
    dp[-1][i] = 0
for i in range(weights[-1], volumn+1):
    dp[-1][i] = values[-1]

for i in range(num_items-2, 0, -1):
    for j in range(volumn+1):
        if j < weights[i]:
            dp[i][j] = dp[i+1][j]
        else:
            dp[i][j] = max(dp[i+1][j], dp[i+1][j-weights[i]]+values[i])

if weights[0] > volumn: print(dp[1][volumn])
else: print(max(dp[1][volumn], dp[1][volumn-weights[0]]+values[0]))

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20010;
int dp[N];
int n,v;
int vi[N];
int wi[N];

int main()
{
    scanf("%d%d",&v,&n);
    for(int i = 0;i<n;i++) scanf("%d%d",&vi[i],&wi[i]);
    
    for(int i = 1;i <= n;i++)
        for(int j = v;j >= 1;j--)
            if(vi[i - 1] <= j) dp[j] = max(dp[j],dp[j - vi[i - 1]] + wi[i - 1]);
    
    cout<<dp[v];
    
    return 0;
}

#include<iostream>
#include<vector>
using namespace std;

int main()
{
    int V,N;
    cin>>V>>N;
    vector<int> dp(V+1);
    vector<int> weight(N+1);
    vector<int> value(N+1);
    for(int i=1;i<=N;i++)
    {
        cin>>weight[i]>>value[i];
    }
    for(int i=1;i<=N;i++)
    {
        for(int j=V;j>=weight[i];j--)
        {
            dp[j]=max(dp[j-weight[i]]+value[i], dp[j]);
        }
    }
    cout<<dp[V];
    return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int main(){
    int n,m;//n个数 m：包体积
    cin>>m>>n;
    if(n==0 || m==0){
        cout<<0;
        return 0;
    }
    vector<int> V;//价值
    vector<int> A;//体积
    int x, y;
	for (int i = 0; i < n; ++i) {
		cin >> x >> y;
		A.push_back(x);
		V.push_back(y);
	}
    vector<int> ans(m+1,0);
     for(int i=1;i<=n;++i){
        for(int j=m;j>0;--j){
            if(j>=A[i-1])
            ans[j]=max(ans[j],V[i-1]+ans[j-A[i-1]]);
        }
    }
    /*
    vector<vector<int>> ans(n+1,vector<int>(m+1,0));
    for(int i=1;i<=n;++i){
        for(int j=1;j<=m;++j){
            if(A[i-1]>j){
                ans[i][j]=ans[i-1][j];
            }else{
                ans[i][j]=max(ans[i-1][j],V[i-1]+ans[i-1][j-A[i-1]]);
            }
        }
    }
    */
    cout<<ans[m];
    
    return 0;
}

def knapsack(V , n , vw ):
    dp=[[0]*(V+1) for _ in range(n+1)]
    for i in range(1,n+1):
        vi=vw[i-1][0]
        wi=vw[i-1][1]
        for j in range(1,V+1):
            if vi>j:
                dp[i][j]=dp[i-1][j]
            else:
                dp[i][j]=max(dp[i-1][j],dp[i-1][j-vi]+wi)
    return dp[-1][-1]
V , n =map(int,input().split())
vw=[]
for _ in range(n):
    v,w=map(int,input().split())
    vw.append([v,w])
print(knapsack(V , n , vw ))

#include <iostream>
#include <vector>

using namespace std;

int main() {
    // Read inputs
    unsigned W, N;  // Weight Limit, Number of items
    cin >> W >> N;
    vector<int> weight;
    vector<int> val;
    for (unsigned i = 0; i < N; i++) {
        int x1, x2;
        cin >> x1 >> x2;
        weight.push_back(x1);
        val.push_back(x2);
    }
    
    // Core code
    vector<int> dp(W + 1, 0);
    for (unsigned i = 0; i < N; i++) {
        for (unsigned w = W; w >= weight[i]; w--) {
            dp[w] = max(dp[w], dp[w - weight[i]] + val[i]);
        }
    }
    
    // Output
    cout << dp[W];
    
    return 0;
}

package main

import "fmt"

func main() {
	var v int
	var n int
	fmt.Scan(&v,&n)
	volumes := make([]int,n)
	values := make([]int,n)
	var volume int
	var value int
	for i:=0;i<n;i++{
		fmt.Scan(&volume,&value)
		volumes[i] = volume
		values[i] = value
	}
	maxValue := knapsack(v,n,volumes,values)
	fmt.Println(maxValue)
}
func knapsack(v,n int,volumes,values []int) int {
	dp := make([][]int,n+1)
	for i:=0;i<=n;i++{
		dp[i] = make([]int,v+1)
	}
	for i:=1;i<=n;i++{
		volume := volumes[i-1]
		value := values[i-1]
		for j:=1;j<=v;j++{
			if j>=volume {
				dp[i][j]=max(dp[i-1][j],dp[i-1][j-volume]+value)
			}else {
				dp[i][j]=dp[i-1][j]
			}
		}
	}
	return dp[n][v]
}
func max(a,b int) int {
	if a>b {
		return a
	}
	return b
}

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        int V = in.nextInt();
        int n = in.nextInt();
        int[][] pack = new int [n + 1][2];
        for(int i = 1; i <= n; i++){
            pack[i][0] = in.nextInt();
            pack[i][1] = in.nextInt();
        }
        int[][] dp = new int[n + 1][V + 1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= V; j++){
                // 此时物品体积大于背包容积，故不能放进背包，因此最大价值为
                if(pack[i][0] > j){
                    dp[i][j] = dp[i - 1][j];
                }
                else{
                    // 此时空间够大，可以选择物品i和不选择物品i
                                        // 不选择，则为dp[i - 1][j]，即为前i-1个物品在空间为j时的最优解

                                        // 选择时，则为前i - 1个物品，在空间为j - 物品i所占空间的最优解
                    dp[i][j] = Math.max(dp[i - 1][j], (dp[i - 1][j - pack[i][0]] + pack[i][1]));
                }
            }
        }
                // 输出整个dp数组
        for(int[] i : dp){
            for(int j : i){
                System.out.print(j + " ");
            }
            System.out.println();
        }
        System.out.println(dp[n][V]);
    }
}

import java.util.Scanner; public class Main{ public static void main(String[] args){
        Scanner sc = new Scanner(System.in); int V = sc.nextInt(); int n = sc.nextInt();
        Thing[] things = new Thing[n]; for(int i=0;i<n;i++){ int v; int w;
            v=sc.nextInt();
            w=sc.nextInt();
            Thing thing = new Thing(v,w);
            things[i]=thing;
        } int[] dp = new int[V+1]; for(int i=0;i<n;i++){ for(int j=V;j>0;j--){ int max = dp[j]; if(j-things[i].vo>=0 && max<things[i].we+dp[j-things[i].vo]){
                    max = things[i].we+dp[j-things[i].vo];
                } if(max>dp[j]){
                    dp[j]=max;
                }
            }
        }
        System.out.println(dp[V]);
    }
} class Thing{ int vo; int we; public Thing(int vo,int we){ this.vo = vo; this.we = we;
    }
}

#include<iostream>
#include<math.h>
using namespace std;
int main(){
    int n,c;
    cin>>c>>n;
    int w[n],v[n],dp[c+1];
    for(int i=0;i<n;i++)
        cin>>w[i]>>v[i];
    for(int j=0;j<=c;j++)
        if(w[0]<=j) dp[j]=v[0];
        else dp[j]=0;
    for(int i=1;i<n;i++)
        for(int j=c;j>=w[i];j--){
            dp[j]=max(dp[j], v[i]+dp[j-w[i]]);
        }
    cout<<dp[c]<<endl;
    return 0;
}

C++实现，时间复杂度O(NV)，空间复杂度O(V)。

#include<bits/stdc++.h>

using namespace std;

int main() {
    int V, N;

    cin >> V >> N;

    vector<int> dp(V + 1, 0);

    vector<int> vVct, wVct;
    vVct.reserve(N + 1);
    wVct.reserve(N + 1);

    int tmpV, tmpW;
    for (int i = 0; i < N; ++i) {
        cin >> tmpV >> tmpW;
        vVct.push_back(tmpV);
        wVct.push_back(tmpW);
    }

    for (int i = 0; i < N; ++i) {
        for (int j = V; j >= vVct[i]; --j) {
            dp[j] = max(dp[j], dp[j - vVct[i]] + wVct[i]);
        }
    }

    cout << dp[V] << endl;

    return 0;
}