Question

Cho một dãy số a[n] và số nguyên s, hãy tìm dãy số dài nhất có tổng bằng s, nếu không có thì xuất “KHONG CO”.(0<n<1000; 0<a[i]<=100; 0<s<5000)

Tên file: Daysos.cpp

Dữ liệu vào: Daysos.inp

Dòng đầu chứa số nguyên n và s

Dòng tiếp theo chứa các số nguyên là phần tử của mảng a

Dữ liệu ra: Daysos.out

Dòng đầu là độ dài của dãy số dài nhất có tổng bằng s

Dòng tiếp theo là giá trị của các phần tử có trong dãy

Daysos.inp	Daysos.out
10 11 10 1 1 2 3 4 11 2 3 1	6 1 1 2 4 2 1
10 11 10 2 4 6 8 8 2 4 4 8	KHONG CO

Ai giúp mình bài này với ạ !

Answer 1

#include <iostream>
#include <fstream>

int main()
{
std::ifstream f("daycon.inp");
int n,s,a[1001],d[100][1001];
f>>n>>s;
for(int i=1;i<=n;i++)
{
f>>a[i];
}
d[0][0]=0;
a[0]=0;
d[1][a[1]]=1;
for(int i=2;i<=n;i++)
{
for(int j=0;j<=s;j++)
{
d[i][j]=d[i-1][j];
if(j==a[i]&&d[i-1][j]<1)
d[i][j]=1;
else
if(a[i]<j&&d[i-1][j-a[i]]>0&&d[i-1][j-a[i]]+1>d[i][j])
d[i][j]=d[i-1][j-a[i]]+1;
}
}
for(int i=n;i>=1;i--)
{
if(d[i][s]!=d[i-1][s])
{
std::cout<<a[i]<<" ";
s-=a[i];
}
}

return 0;
}